树状数组浅谈

【树状数组，就是这么简单！】https://www.bilibili.com/video/BV12a411i7rP?vd_source=e583d26dc0028b3e6ea220aadf5bc7fe

视频内容

树状数组1

问题1：如何构造树状数组？

首先我们假设树状数组已经构造好了（假设是c数组），考虑给第x个数加上k的函数怎么写

void add(int x,int k){//第x个数加kint tmp = x;while(x <= n){c[x] += k;x = x + lowbit(x);} }

给第x个数加k，要给c[x]和c[x]的全部后继都加上k，所以利用while循环，找到c[x]的全部后继，都加上k。

那么构造的时候，每读入一个元素a[i]，也进行这个操作。相当于这个位置原本是0，加上了a[i]

for(int i = 1;i <= n;i ++){cin >> a[i];//构造树状数组 int tmp = i;while(tmp <= n){c[tmp] += a[i];tmp = tmp + lowbit(tmp);//后继 }}

当然，也可以直接利用add函数add(i,a[i])。

问题2，如何求区间和[x,y]

先找r前驱，把所有的前驱都加起来，是前y项的和；同理求出前x-1项的和，两者相减就是区间和了

int sum(int x,int y){//先求前缀和sum[y],再求sum[x - 1],相减即可int sumy = 0,sumx = 0;while(y){//找前驱 sumy += c[y];y = y - lowbit(y);}x = x - 1;while(x){sumx += c[x];x = x - lowbit(x);}return sumy - sumx;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int lowbit(int i){return i&(-i);
}
int a[1100000];
int c[1100000];//前驱c[i-lowbit(i)],后继c[i+lowbit(i)] 
int n,m;
void add(int x,int k); 
int sum(int x,int y);
int main(void){//sum[7] = c[7] + c[6] + c[4];//int n,m;cin >> n >> m;//n个数据，m组操作 for(int i = 1;i <= n;i ++){cin >> a[i];//构造树状数组 int tmp = i;while(tmp <= n){c[tmp] += a[i];tmp = tmp + lowbit(tmp);//后继 }}while(m --){int a,b,c;cin >> a >> b >> c;if(a == 1){//addadd(b,c);}else{cout << sum(b,c) << endl;}}}
void add(int x,int k){//第x个数加kint tmp = x;while(x <= n){c[x] += k;x = x + lowbit(x);} }int sum(int x,int y){//先求前缀和sum[y],再求sum[x - 1],相减即可int sumy = 0,sumx = 0;while(y){//找前驱 sumy += c[y];y = y - lowbit(y);}x = x - 1;while(x){sumx += c[x];x = x - lowbit(x);}return sumy - sumx;
}

树状数组2

由于线段树一般只能解决单点修改（修改某一个元素的值）和区间查询（求某个区间的和），而本题需要对区间修改和单点查询，因此构造原来数组的树状数组是不行的

方法：首先构建原来数组的差分数组，再对差分数组构造树状数组，由于操作1是给[x,y]的每个元素都加k，对于差分数组来说只需要改变第x个元素的值和第y+1个元素的值，相当于单点修改。操作2是输出某个数x的值，对于差分数组来说是前x项和，也就是区间查询（求区间和），这样就可以利用树状数组解决此题辣！

#include<bits/stdc++.h>
using namespace std;
int b[500003],c[500003];
int n,m;
int lowbit(int x){return x&(-x);
}
void add(int i,int k); 
int sum(int x);
int main(void){cin >> n >> m;int x,y = 0;for(int i = 1;i <= n;i ++){cin >> x;b[i] = x - y;//add(i,b[i]);//第i个数加上b[i] y = x;}while(m --){int op;cin >> op;if(op == 1){int x,y,k;cin >> x >> y >> k;add(x,k);add(y + 1,-k);}else{int x;cin >> x;cout << sum(x) << endl;}}}
void add(int i,int k){int tmp = i;while(tmp <= n){c[tmp] += k;tmp = tmp + lowbit(tmp);}
}int sum(int x){//求差分数组的前x项和 int tmp = x,result = 0;while(tmp){result += c[tmp];tmp = tmp - lowbit(tmp);}return result;
}

代码的差分数组和差分的树状数组一起构建，没有开辟空间给原来数组（因为不需要）。