树状数组模板题：一本通1535

2021-04-20 00:31

阅读：511

标签：int scanf 两种计算 mic 数组开始求和 loading

技术图片

这道题是一道树状数组的模板题，主要考察树状数组的单点修改和区间求和的两种基本操作，只要写好对应的函数，按照读入的内容进行操作即可。首先写好lowbit、update、sum函数。因为之前已经写过了这些函数的写法，这里不再陈述。

int lowbit(int x){
    return x&(-x);
}
void update(int x,int v){//在序列第x个位置加上a，并在数状数组中修改相关元素 
    while(xn){
        c[x]+=v;
        x+=lowbit(x);
    }
    return;
}
int sum(int x){//计算序列第一个位置到第x个位置的区间和 
    int res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

然后写主函数即可。读入n、m，以及a数组来存储原数组。对树状数组c数组初始化为0，然后依次对a数组中的数进行update操作。接下来对于每一个操作输入k，若k=1，对第a个数进行update操作加b，若k=0，读入a和b，输出sum(b)-sum(a-1)的值即可。

下面是完整代码：

 1 #include 2 int c[100005];
 3 int n,m,op,a,b,v,i;
 4 int lowbit(int x){
 5     return x&(-x);
 6 }
 7 void update(int x,int v){//在序列第x个位置加上a，并在数状数组中修改相关元素 
 8     while(xn){
 9         c[x]+=v;
10         x+=lowbit(x);
11     }
12 }
13 void update(int x){
14     int res=0;
15     while(1){
16         res+=c[x];
17         x-=lowbit(x);
18     }
19     return res;
20 }
21 int main(){
22     scanf("%d %d",&n,&m);
23     for(i=1;i=n;i++){
24         scanf("%d",&v);
25         update(i,v);
26         //开始时每个元素初始值为0，读入序列时直接在对应位置加上v即可 
27     }
28     for(i=1;i){
29         scanf("%d %d %d",&op,&a,&b);
30         if(op==0){
31             printf("%d\n",sum(b)-sum(a-1));
32         }else{
33             update(a,b);
34         }
35     }
36     return 0;
37 }

树状数组模板题：一本通1535

标签：int scanf 两种计算 mic 数组开始求和 loading

原文地址：https://www.cnblogs.com/qianr/p/13253610.html

上一篇：LeetCode 108. 将有序数组转换为二叉搜索树

下一篇：Spring入门案例

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：树状数组模板题：一本通1535
文章链接：http://soscw.com/index.php/essay/76899.html

亲，登录后才可以留言！

树状数组模板题：一本通1535

评论

热门文章

推荐文章

最新文章

置顶文章