树状数组
总结一下树状数组。
作用
树状数组通常用于解决区间问题，总的来说它的用途没线段树广，但是常数比线段树小而且写法较为简单，所以还有一定用途。
原理
树状数组的一个核心是lowbit计算，其具体就是
int lowbit(int x)
首先有一点，计算机内储存整型类型变量试用补码储存的。
正数的补码是原码，负数的补码是将其原码除符号位外的所有位取反后加1。
那lowbit计算的结果是什么呢？
这里拿数字26举例。
26 补码：00011010 -26 原码：10011010 反码：11100101 补码：11100110
lowbit(26)=00000010
可以看出0010是26二进制下最右端1的位置。
通过感性理解，我们就可以发现lowbit的功能就是找出一个数二进制下最右端1的位置。
通过lowbit我们可以构造出一个怎样的数据结构呢？
单点修改区间查询
单点修改区间查询是树状数组最基本的功能。
树状数组的功能是以lgn的复杂度完成单点修改和查询1~n的和的操作。
首先我们要知道树状数组f[n]的含义是什么。
\[f[n]=\sum_{i=n-lowbit(n)+1}^n a[i] \]然后我们只需要对每个操作进行模拟就行了
单点修改
void add(int i,int x)
区间查询
int qry(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=f[i];
return res;
}ans=qry(r,l-1);
区间修改单点查询
这里主要运用了差分的思想。
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int lowbit(int x){return x&-x;}
int n,m;
int f[N];
void add(int i,int x){for(;i<=n;i+=lowbit(i))f[i]+=x;}
int qry(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=f[i];
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;++i){scanf("%d",&x);add(i,x);add(i+1,-x);}
while(m--){
int o,x,y,k;
scanf("%d",&o);
if(o==1){scanf("%d%d%d",&x,&y,&k);add(y+1,-k);add(x,k);}
else {scanf("%d",&y);printf("%d\n",qry(y));}
}
return 0;
}
区间修改区间查询
通过一些构造树状数组也是可以完成区间修改区间查询的，但是最好平时还是用线段树会好一些，因为会比较直观。
这里放上代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}
int lowbit(int x){return x&-x;}
ll c1[N],c2[N];
int n,m;
ll add(int x,ll y){for(int i=x;i<=n;i+=lowbit(i))c1[i]+=y,c2[i]+=y*x;}
ll get(int x){ll res=0;for(int i=x;i;i-=lowbit(i))res+=c1[i]*(x+1)-c2[i];return res;}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){ll x=read();add(i,x);add(i+1,-x);}
while(m--){
int o=read();
if(o==1){int l=read(),r=read();ll z=read();add(l,z);add(r+1,-z);}
else {int l=read(),r=read();printf("%lld\n",get(r)-get(l-1));}
}
return 0;
}