下面是树状数组的学习笔记：
目录：
（(1)）什么是树状数组
（(2)）如何使用树状数组
（(3)）树状数组的应用
（(1)）什么是树状数组
在解题过程中，有时候要维护一个数组的前缀(S[i]=A[1]+A[2]+···+A[i])。但是如果我们修改了任何一个(A[i])，(S[1]、S[2]、S[3]···S[i])的值都会相应改变。如果我们循环维护每一个(S[i])，那样就太慢了。于是我们要考虑使用数据结构来进行优化。树状数组就是这样一个数据结构！
首先介绍一下前置知识：
根据任意正整数关于(2)的不重复次幂的唯一分解性质，若一个正整数(x)的(2)进制表示为(10101)，其中等于(1)的位是(0,2,4)则正整数可以被分解为(2^4+2^2+2^0)。那么，区间([1,x])就可以被分为(logx)各小区间
长度为(2^4)的区间为([1,2^4])；长度为(2^2)的区间为([2^4+1,2^4+2^2])；长度为(2^0)的区间为([2^4+2^2+1,2^4+2^2+2^0])。
树状数组就是这样一种结构，它的基本用途就是维护序列的前缀和。对于区间([1,x])树状数组将其分为(logx)个子区间，从而满足快速询问区间和。
由上文可知，这些子区间的共同特点是：若区间结尾为(R)则区间长度就为(R)的“二进制分解”下最小的(2)的次幂，我们定义为(lowbit(R))。对于给定的(A)序列，我们维护一个(c)数组，其实这个(c)数组就是我们所说的树状数组。(c[i])中储存的是(sum A[i]space (iin [x-lowbit(x)+1,x]))。
树状数组的存储结构如下图：
值得注意的是，这样的树状结构满足以下的4个性质：
(1). 每个内部节点(c[i])保存以它为根的子树中所有叶节点的和
(2). 每个内部节点(c[i])的子节点个数为(lowbit(i))的大小
(3). 除树根外，每个内部节点(c[i])的父节点是(c[i+lowbit(i)])
(4). 树的深度为(O(logN))
（2）如何使用树状数组
接下来就讲到实现方面了，树状数组的实现是与上面(4)个性质分不开的。
第一部分：求(lowbit(n))
(lowbit(n))表示去除非负整数(n)在二进制下最低位的(1)以及它后边的(0)构成的数值。于是(lowbit(n)=n)&((-n))，但是这是怎么来的呢，请听我细细道来（其实我也不知道）
设(n>0)，(n)的第(k)位是1，其余都是(0)
为了实现(lowbit)运算，先把(n)取反，此时第(k) 位变为(0)，其余都是(1)。再另(n=n+1)，此时因为进位 ，第(k)位变为(1)，其余都为(0)。在上面的取反加一操作后，(n)的第(k+1)到最高位恰好与原来相反，所以(n)&$n+1$仅有第$k$位为$1$，其余位都是$0$。而在补码表示下，(n=-1-n)，因此，(lowbit(n)=n)&((-n))
下面是这一部分的代码实现：
int lowbit(int n)
{
return n&(-n);//这句话水的不能再水了，不说了
}
第二部分：单点操作（就是对某个元素进行加法操作，下面以加法为例）
树状数组支持单点操作，根据性质(1、3)。每一个内部节点(c[i])保存以它为根的子树中所有叶节点的和，这就说明，我们一旦对$A[i] (进行改动，就一定要对)c[i](进行改动，并且将所有)c[i](的父亲节点改动。那么如何找到)c[i](的父亲节点呢？其实我们只需要将)i(更新为)i+lowbit(i)$，就可以完成对父亲节点的遍历了。
下面是这一部分的代码实现：
void update(int x,int y)//表示A[x]加y时维护c数组
{
for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
第三部分：查询前缀和
树状数组支持单点修改和区间查询，下面介绍一下区间查询前缀和的方式：
在这里我们所定义的前缀和，实际上就是(sum A[i] (iin [1,x]))。按照（(1)）中所讲，应该将$[1,x] (分成)logn(个小区间，每个小区间的区间和都已经保存在数组)c$中。
下面是这一部分的代码实现：（即(O(logn))时间查询前缀和）
int sum(int x)//求1~x的前缀和
{
int ans=0;//用ans存储前缀和
for(;x;x-=lowbit(x)) ans+=c[i];//遍历子节点，累加ans
return ans;//最后的答案就是ans
}
第四部分：统计(A[x]···A[y])的值
调用以上的(sum)函数，可以求出(A[x]···A[y])得值就是(sum(y)-sum(x-1))
第五部分：扩展（多维树状数组）
由于处理每一个树状数组的复杂度是(O(logn))。所以它可以扩充到(m)维，这样一来，处理树状数组的复杂度就提升到了(O(log^mn))，若(m)不大的时候，这个复杂度是可以被接受的。但是到底如何实现呢？
其实，扩充树状数组的方式就是讲原来的一个循环改成(m)个循环，这一部分的代码如下：
void update(int x,int y,int z)//将(x,y)的值加上z
{
int i=x;
while(i<=n)//如果m更大，再多写几个while
{
int j=y;
while(j<=m)
{
c[i][j]+=z;
j+=lowbit(j);
}
i+=lowbit(i);
}
}
int sum(int x,int y)
{
int res=0,i=x;
while(i>0)
{
int j=y;
while(j>0)
{
res+=c[i][j];
j-=lowbit(i);
}
i-=lowbit(i);
}
return res;
}
第六部分：注意事项
要注意树状数组绝对不能出现下标为(0)的状况，因为啥啊，因为(lowbit(0)=0)啊！
（(3)）树状数组的应用
树状数组的应用有很多，下面重点将洛谷上两个模板题讲解一下
【题目描述】
如题，已知一个数列，你需要进行下面两种操作：
(1).将某一个数加上(x)
(2).求出某区间每一个数的和
直接上代码吧，就是彻彻底底的板子题
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=500010;
int n,m;
int a[maxn],c[maxn];
int h,q,k;//我没得设变量啊TwT
int lowbit(int x)//就是算lowbit(x)
{
return x&(-x);
}
void update(int x,int y)//就是将y插入到x中
{
for(;x<=n;x+=lowbit(x))
{
c[x]+=y;
}
}
int sum(int x)//就是计算A[1]+A[2]+···+A[x]的值
{
int ans=0;
for(;x;x-=lowbit(x))
{
ans+=c[x];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
update(i,a[i]);
}
while(m)//循环读入数据
{
m--;
scanf("%d",&h);
if(h==1)//h是对类型的判断
{
scanf("%d%d",&q,&k);
update(q,k);
}
if(h==2)
{
scanf("%d%d",&q,&k);
printf("%d
",sum(k)-sum(q-1));
}
}
return 0;
}
上面的这道题是典型的树状数组“单点修改，区间查询题”。但是下面一道题就不是这样了！
【题目描述】
如题，已知一个数列，你需要进行下面两种操作：
(1).将某区间每一个数数加上(x)
(2).求出某一个数的值
【题目分析】
诶？这道题好像是“区间修改，单点查询”的题额，怎么做呢？我们引入一个叫做差分的概念：
假设(A[]=){(1,5,3,6,4)}，(B[]=){(1,4,-2,3,-2)}
我们可以发现，如果规定(A[0]=0)，那么可以满足(B[i]=A[i]-A[i-1])，并且(A[i]=B[1]+B[2]+···+B[i])。
如果我们在区间([2,4])上加上(2)，按照相同的规则进行处理，可以得到(B[]=){(1,7,-2,3,)}，只有(B[2])和(B[5])有改动
于是我们可以得到一个规律，即：对于(A),将区间([l,r])中的每一个数都加上一个数(x)，(B[l]+=x;B[r+1]-=x)
于是我们可以开一个树状数组维护差分值，每次只需要将(l)和(r+1)进行操作，最后将需要查询的(A)值转化为(B)值求和就可以得到了！
下面请食用代码:
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=500010;
int n,m;
int a[maxn],c[maxn];
int h,q,k,d;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
for(;x<=n;x+=lowbit(x))
{
c[x]+=y;
}
}
int sum(int x)
{
int ans=0;
for(;x;x-=lowbit(x))
{
ans+=c[x];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
while(m)
{
m--;
scanf("%d",&h);
if(h==1)
{
scanf("%d%d%d",&q,&k,&d);
update(q,d);
update(k+1,-d);
}
if(h==2)
{
scanf("%d",&q);
printf("%d
",a[q]+sum(q));
}
}
return 0;
}
/*
相信大家已经发现了，这段代码与前一段没有什么太大的区别，其实就是将读入增加了一个，输出减少了一个罢了
*/
(end)