浅谈树状数组
一、这玩意儿有嘛用？
树状数组，顾名思义，即结构为树形的一个数组。至于它能解决的问题， 主要是对于单点的修改或是单点的查询 等等，题目有下面两种：
（1）已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的值
栗子1： 树状数组1
（2）已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的值
栗子2： 树状数组2
当然，与此有关的变式还有很多，（但本蒟蒻都不会） 下面，主要讲一讲 （最简单的） 树状数组。
二、什么是树状数组？
空谈不如举个栗子
如图，A[i] 是输入的数据，C[i]就是我们所说的树状数组。
可以看到，树状数组是一个类似于二叉树的形状，其中，叶节点维护的是原本数据的值，而非叶节点维护的是两个子树的和。说白了，就类似于一种变相的前缀和操作罢了。
一个关于树状数组详解的网站：树状数组 数据结构详解与模板
三、代码实现：
树状数组的核心程序，在于一段很短的代码。这段程序的功能在于：返回如上图所示的某一点在树状数组中的左子树的下标（右子树下标就是自身的下标），从而实现向下（或向上）累加的操作。
一个简介的程序，需要用到位运算的一些知识：
关于位运算：位运算小结
核心程序：
int lowbit(int x)
{
return x&(-x);
}简洁而又功能强大。
关于这段程序的解释：
x&（-x），其中 -x 是 x 的相反数。我们输入进来的数都是正整数，那么取相反数就一定是一个负数，而在 c++ 中，负数存储是以补码的形式存储的。
正数的源码、反码、补码都相同，如：
+1 = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001（64bits）
负数的原码的最高位为1；反码为原码符号位不变，其他位取反；补码为反码+1
原码：-1=1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001
反码：-1=1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110
补码：-1=1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
计算机中负数的存储为补码
移码：不管正负数，只要将其补码的符号位取反即可
//原文链接：https://blog.csdn.net/u012868357/article/details/79023076
原码，补码，反码
分为：正数 和 负数（包括正浮点数，和负浮点数）
规定最高位位符号位正数为0，负数为1（原因下文解释）
原码：10进制转换成2进制是原码，只不过正数的原码是本身符号位为0，负数的原码符号位为1（以下篇幅均以单字节为例：10进制1的原码是0000 0001，10进制-1的原码是1000 0001）。
反码： 正数的反码是本身，负数的反码是负数的原码0变为1,1变为0 （-1的原码是1000 0001 它的反码就是 1111 1110，）。（注意负数求反码时候的符号位不参与变换）。
补码： 正数的补码是本身，负数的反码就是负数的反码加一 （-1的原码是1000 0001 它的反码就是 1111 1110 它的补码就是 1111 1111）。
总结：正数的原码，反码 ，补码三值合一， 负数的原码，反码，补码不同。
/*原文链接：https://blog.csdn.net/littesss/article/details/70495810*/关于建树
建树有一个非常简单的操作，即在输入的同时进行操作，但有时，使所有的数值都为0可能更加简便，这时便无需建树操作。 下面的两个栗子就是一个很好的体现。
建树操作：
void update(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=y;
//将该点在树中的父节点都更新一遍
}两个栗子
树状数组1
关于上面的栗子1：
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500009
int n,c[N],w;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=y;
//将该点在树中的父节点都更新一遍
}
int getsum(int x)
{
int sum=0;
for(int i=x;i>0;i-=lowbit(i))
sum+=c[i];
return sum;
}
int main()
{
int m,a,x,y;
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&w);
update(i,w);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&x,&y);
if(a==1)
update(x,y);
if(a==2)
printf("%d\n",getsum(y)-getsum(x-1));
//利用前缀和的思想来进行输出
}
return 0;
}树状数组2
关于上面的栗子2的程序：
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500009
typedef long long ll;
int n,m,a;
ll c[N],w[N];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
//在存储时，要i要＋lowbit(i)，
//从而使其父亲的值得到更新
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=y;
}
//利用 c 数组来存储差分
}
int getsum(int x)
{
int sum=0;
//如果该店的值有更新，则存储的更新信息一定是在该点的前面
//所以i要-lowbit(i)
for(int i=x;i>0;i-=lowbit(i))
sum+=c[i];
//如果该点需要更新，则一定能搜索到存储更新信息的点，
//从而累加使sum存储该信息
//如果该点前面的更新区间不包括该点，
//则差分可以使两次累加的总和== 0，从而保证了结果的正确性
return sum;
}
int main()
{
ll x,y,z;
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]); // 存储下原来的值
for(int i=1;i<=m;i++)
{
scanf("%d%lld",&a,&x);
if(a==1)
{
scanf("%lld%lld",&y,&z);
// 差分的思想
update(x,z);
update(y+1,-z);
}
if(a==2)
printf("%lld\n",w[x]+getsum(x));
//原数值 加上 差分得到的修改值 就是最终的结果
}
return 0;
}