树状数组 学习笔记
1.前置知识
二叉树。
分治。
前缀和。
2.树状数组
其实就是前缀和用二叉树做。
将二叉树右对齐即可。
如这样一颗二叉树
将它变成这样
如下图（绿色为 \(C\) 数组，红色为 \(a\) 数组）
即\(C_{1}=a_{1}\)
\(\,\,\,\,\,\,C_{2}=a_{1}+a_{2}\)
\(\,\,\,\,\,\,C_{3}=a_{3}\)
\(\,\,\,\,\,\,C_{4}=a_{1}+a_{2}+a_{3}+a_{4}\)
\(\,\,\,\,\,\,C_{5}=a_{5}\)
\(\,\,\,\,\,\,C_{6}=a_{5}+a_{6}\)
\(\,\,\,\,\,\,C_{7}=a_{7}\)
\(\,\,\,\,\,\,C_{8}=a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}\)
试试找规律？
全部转为二进制
0001 001
0010 001 010
0011 011
0100 001 010 011 100
0101 101
0110 101 110
0111 111
1000 001 010 011 100 101 110 111
不难发现 \(C_{i}\) 中数的个数为\(2\) 的 \(i\) 的二进制中 \(1\) 的最右边的位置后的 \(0\) 的个数 次幂。
读起来很绕口对吧，举个例子，如 \((0100)_{2}\)，它的最右边的 \(1\) 后有 \(2\) 个 \(0\)，\(2^{2}=4\)，所以 \(C_{(0100)_{2}}\) 中数的个数为 \(4\)。
那么问题来了，如何求 \(i\) 的二进制中最右边的 \(1\) 的位置呢？
给出如下代码
inline int lowbit(int x)
{
return x&(-x);
}
解释一下。
-x 就是将 \(x\) 连同符号位一起反转再加一的结果，如 \(0010\) 的反码为 \(1110\)。
&运算 不用解释了吧。
运算x&(-x)，举个例子，\(0101\) 的反码为 \(1011\)，与 \(0101\) 进行 &运算 得 \(0001\) ，也就是 \(1\)，这就找到了 \(i\) 的二进制中最右边的 \(1\) 的位置。
3.单点更新，区间查询
inline void update(int x,int y)//表示将a[x]+y
{
for(register int i=x;i<=n;i+=lowbit(i)) a[i]+=y;//每层更新
}
将每层与 \(a_{x}\) 相关的值更新一下。
inline int getsum(int x)//求C[x]的值
{
ans=0;
for(register int i=x;i;i-=lowbit(i)) ans+=a[i];
return ans;
}
将每层与 \(C_{x}\) 相关的值相加求和。
然后用前缀和做就行啦。
即区间 \((x,y)\) 的值为 getsum(y)-getsum(x-1)。
模板题1
模板题2
模板题3
仅给出 模板1 的代码（其实都差不多）。
#include
using namespace std;
int ans;
int n,m;
int x,y,z;
int num;
int a[500002];
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void print(int x)
{
write(x);
putchar('\n');
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void update(int x,int y)
{
for(register int i=x;i<=n;i+=lowbit(i)) a[i]+=y;
}
inline int getsum(int x)
{
ans=0;
for(register int i=x;i;i-=lowbit(i)) ans+=a[i];
return ans;
}
int main()
{
n=read();m=read();
for(register int i=1;i<=n;++i)
{
z=read();
update(i,z);
}
for(register int i=1;i<=m;++i)
{
num=read();x=read();y=read();
if(num==1) update(x,y);
else print(getsum(y)-getsum(x-1));
}
return 0;
}
4.区间更新，单点查询
inline int lowbit(int x)
{
return x&(-x);
}
inline void update(int x,int y)
{
for(register int i=x;i<=n;i+=lowbit(i)) a[i]+=y;
}
inline int getsum(int x)
{
ans=0;
for(register int i=x;i;i-=lowbit(i)) ans+=a[i];
return ans;
}
这些代码不会变。
多了个差分。
差分讲解一下。
有如下 \(a\) 数组
现在要将 \((2,5)\) 这个区间里的值都加一。
直接循环复杂度肯定不优。
考虑将 \(a_{2}+1,a_{5+1}-1\)
即原数组为
这样在查询时可以定一个 \(ans\)，边循环边加，然后输出。
a[x]--,a[y+1]++ //差分
for i←1 to n+1
do s+=a[i] //统计
write(s,' ') //输出
\(\texttt{Q}\):为何要这样差分？
\(\texttt{A}\):在查询时将值赋为当前正确的值，在查询完减去即可。
于是可得差分代码
inline void add(int l,int r,int x)//对(l,r)的区间进行差分
{
update(l,x);update(r+1,-x);
}
//（应该不难理解吧）
模板题
直接贴代码。
#include
using namespace std;
int ans;
int n,m;
int x,y,k;
int now,last;
int num;
int a[500002];
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void print(int x)
{
write(x);
putchar('\n');
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void update(int x,int y)
{
for(register int i=x;i<=n;i+=lowbit(i)) a[i]+=y;
}
inline int getsum(int x)
{
ans=0;
for(register int i=x;i;i-=lowbit(i)) ans+=a[i];
return ans;
}
inline void add(int l,int r,int x)
{
update(l,x);update(r+1,-x);
}
int main()
{
n=read();m=read();
for(register int i=1;i<=n;++i)
{
now=read();
update(i,now-last);
last=now;
}
for(register int i=1;i<=m;++i)
{
num=read();
if(num==1)
{
x=read();y=read();k=read();
add(x,y,k);
}
else
{
x=read();
print(getsum(x));
}
}
return 0;
}
5.总结
参考资料：
https://blog.csdn.net/bestsort/article/details/80796531
https://www.luogu.com.cn/blog/kingxbz/shu-zhuang-shuo-zu-zong-ru-men-dao-ru-fen
练习：求逆序对。
#include
#define int long long
using namespace std;
struct arr
{
int sum,num;
}A[500002];
int a[500002];
int f[500002];
int n;
int x;
int ans;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void print(int x)
{
write(x);
putchar('\n');
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void update(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i)) f[i]+=y;
}
inline int getsum(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=f[i];
return sum;
}
bool cmp(arr x,arr y)
{
if(x.sum!=y.sum) return x.sum