数据结构之树状数组—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; }
简单易懂,多好。

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