列公子

用户名：lielielie

访问量：10582

签　名：

等　　级
排　　名	1692
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)
浏览：273

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)
浏览：2110

蓝桥杯算法提高- 拿糖果动态规划 (C++)
浏览：444

你可能喜欢

蓝桥杯分苹果树状数组

　　作者: 列公子　　　　发表时间：2020-03-01 00:13:23 浏览：231　|　评论：0　

原题链接：蓝桥杯算法提高VIP-分苹果

# [1501] 分苹果  树状数组 区间更新 单点查询

## 1. 树状数组
- 树状数组的索引从**1**开始。
- 树状数组 ```int c[maxn]``` 中的 ```c[i]``` 表示**索引**位于 ```[ i - lowbit(i) + 1,   i ]```范围内的数**被加上了多少**。
- 树状数组的值初始化为 0

## 2. 树状数组的区间更新
```void  update( int x,  int v )``` 将索引位于 ```[1,  x]``` 的值加上 ```v```

##  3. 树状数组的单点查询

```int getSum( int x )``` 返回 索引 为 ```x``` 的元素的值

## 4. 完整代码 (AC)
```cpp
// 蓝桥杯题库 算法提高 1501 分苹果
// 线段树
#include <cstdio>
#define lowbit(x) (x & (-x))
const int maxn = 100010;

//int nums[maxn];      // 原始数组
int c[maxn];        // 树状数组
int N, M;

void update(int x, int v){      // 将 1~x 都加一
    for (int i = x; i > 0; i -= lowbit(i)){
        c[i] += v;
    }
}

int getSum(int x){
    int sum = 0;
    for (int i = x; i <= N; i += lowbit(i))
        sum += c[i];
    return sum;
}

int main(){
    scanf("%d%d", &N, &M);
    while (M--){
        int s, e, num;
        scanf("%d%d%d", &s, &e, &num);
        update(e, num);     // 1 ~ e 所有元素加 num
        update(s-1, -num);  // 1~ s-1 所有元素减 num, 实现 s~e 的元素加 num
    }
    for (int i = 1; i <= N; i++)
        printf("%d ", getSum(i));
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列（C语言代码）

不容易系列2 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯分苹果树状数组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言训练-求素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

哥德巴赫曾猜测（C语言代码）

1014题解

The 3n + 1 problem （C语言代码）

逆反的01串（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了

列公子

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

不容易系列2 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯 分苹果 树状数组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言训练-求素数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

1014题解

The 3n + 1 problem （C语言代码）

逆反的01串 （C语言代码）

1063题 初学者，求帮忙看下,不知道哪错了

C二级辅导-阶乘数列（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

蓝桥杯分苹果树状数组

　　评论区

C语言训练-求素数问题（C语言代码）

哥德巴赫曾猜测（C语言代码）

逆反的01串（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了