洛谷P3374树状数组题解--zhengjun

洛谷P3374树状数组题解--zhengjun数据结构之树状数组 zhengjun P3374 题目 树状数组 1 题目描述 已知一个数列 你需要进行下面两种操作 将某一个数加上 x 求出某区间每一个数的和 输入格式 第一行包含两个正整数 n mn m 分别表示该数列数字的个数和操作的总个数 第二行包含

大家好,我是讯享网,很高兴认识大家。

数据结构之树状数组—zhengjun

P3374题目(树状数组1)

题目描述:

已知一个数列,你需要进行下面两种操作:

将某一个数加上 x

求出某区间每一个数的和

输入格式

第一行包含两个正整数 n,mn,m,分别表示该数列数字的个数和操作的总个数。

第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 mm 行每行包含 33 个整数,表示一个操作,具体如下:

1 x k 含义:将第 x 个数加上 k

2 x y 含义:输出区间 [x,y] 的和

输出格式

输出包含若干行整数,即为所有操作 2 的结果。

输入输出样例
输入
5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4 

讯享网
输出
讯享网14 16 

树状数组的功能

树状数组,是一个查询修改的复杂度都为log(n)的数据结构。


讯享网

 你或许还不理解,这玩意为什么长这样?那么,就用计算机的语言来解释吧(二进制)! 

理解

重点来了
第一层:
讯享网 (0001)1的父亲是(0010)2; (0011)3的父亲是(0100)4; (0101)5的父亲是(0110)6; (0111)7的父亲是(1000)8; ————都以1结尾,并且都加上了1!!! 
第二层:
 (0010)2的父亲是(0010)4; (0110)6的父亲是(1000)8; ————都以10结尾,并且都加上了10!!! 
第三层:
讯享网 (0100)4的父亲是(1000)8; ————都以100结尾,并且都加上了100!!! 
你一定找到规律了!
 在第几层,它的父亲就是加上1<<(层数-1); 或者是,加上它最低位的一个1! 那么,是不是又增加了复杂度呢? 其实不是,只要一个简短的函数: #define lowbit(x) ((x)&(-x)) 
----------------没错!这就是树状数组的核心。

但是,区间求和时又该怎么办呢?

讯享网 0111--7 减去1 0110--6 减去10 0100--4 减去100 

每次减去的不正是当前编号的 l o w b i t lowbit lowbit吗?

那么 4 4 4再减,就变成了 0 0 0,只要一个 w h i l e while while不就解决了吗?

问题

如果是 4 − 7 4-7 4−7怎么办呢?

其实很简单:用 1 − 7 1-7 1−7减去 1 − 3 1-3 1−3不就可以了吗?

代码实现

用数组 c c c来储存这棵树。

加值:

只需从它本身开始加,连续加上 l o w b i t lowbit lowbit
来求它的父亲,并把它的父亲也加上这个值不就行了吗?

区间求和:

若要 x − y x-y x−y的和;

分别用这两个数( x x x和 y − 1 y-1 y−1)做一遍:

 用sum存储和, 将sum加上当前的c[i]; 再减去lowbit(i) 重复执行不就行了吗?(判断是否已减到0) 

代码(未压行)

讯享网#include<cstdio> #define maxn  #define lowbit(x) ((x)&(-x)) #define read(n) scanf("%d",&n)//传说中的最牛的快读 int n,m; int a[maxn],c[maxn]; void update(int rt,int x) { 
    while(rt<=n) { 
    c[rt]+=x; rt+=lowbit(rt); } return; } int query(int rt) { 
    int sum=0; while(rt) { 
    sum+=c[rt]; rt-=lowbit(rt); } return sum; } int main() { 
    read(n),read(m); for(int i=1;i<=n;i++) read(a[i]),update(i,a[i]);//建树时只是将原来的0加上a[i]。 for(int i=1;i<=m;i++) { 
    int x,y,z; read(x),read(y),read(z); if(x==1)//修改 { 
    update(y,z); } else//查询 { 
    printf("%d\n",query(z)-query(y-1)); } } return 0; } 

简单易懂,多好。

Thank you!

--------郑钧

小讯
上一篇 2025-01-20 09:05
下一篇 2025-01-29 09:26

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/113718.html