树状数组（学习小结）

本文主要是介绍树状数组（学习小结），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树状数组

树状数组是一种数据结构，它可以高效处理对一个存储数字的列表进行更新和维护前缀和

已知一个长度为n的数组，现在要实现以下操作：
更新某个位置的值，查询前i个数的和，查询区间[i,j]的和

upData(i, val): 在i位置加上val
query(i)：查询区间从第一个数到第i个数的和
getSum(i, j): 计算第i个数到第j个数的和

树状数组和线段树

树状数组可线段树可以说是亲兄弟了，但他俩还是有一定区别的：
树状数组有的操作，线段树一定有；
线段树有的操作，树状数组不一定有。
那选择线段树不就万事OK了？
答案是没必要，树状数组的代码要比线段树短得多，思路也清晰，能用树状数组就没必要建线段树，就像计算1+1，没必要使用大数加法去计算。

一般的树，比如二叉树，是这样子的：
在这里插入图片描述
现在变一下形，这就是树状数组了：

如果把空的框框都去掉，把C[2],C[4]这些往下压，你会发现C[ ]数组最后在一条线上，与下面的A[ ]数组是对应的
由图可知：
C[1] = A[1]
C[2] = C[1]+A[2] = A[1] + A[2]
C[3] = A[3]
C[4] = C[2]+C[3] + A[4] = A[1]+A[2]+A[3]+A[4]
…
假如这是一棵树，那么C[ i ] 记录的是它两个子节点的和，叶子节点就是它本身，如果我现在要更新A[3]，那么C[4]和C[8]也同样要被更新。

这里和前缀和有点像，但这里并不是每一个C[i]都表示第1个数到第i个数的和，比如C[3]就只表示A[3]的值，而不是A[1]+A[2]+A[3]

看到这里你可能会问了，为什么C[1],C[2],C[3]…的位置是这样的(为什么C[2]表示的是前两个数的和，C[3]却只表示A[3]的值）？
这就是接下来要说的树状数组的构造。

树状数组的构造

所谓树状数组，首先要明白它其实并不是一棵树，它是用数组来模拟树形结构。
图中把空的框框都去掉，把C[2],C[4]这些往下压，你会发现C[ ]数组最后在一条线上，与下面的A[ ]数组是对应的
树状数组的存储与数的二进制有关。

我们先看更新：
更新A[i]的时候，连带的要把它会影响到的C[ ]也更新掉，比如A[1]的值，那么不止C[1]的值更新了，C[2],C[4],C[8]的值都得更新；更新A[5]的时候，C[5],C[6],C[8]都得更新,那么要怎么实现这一更新操作呢？这里就和lowbit有关了。

void upData(int i, int val) //将i位置加上val
{for( ; i <= n; i += (i & (-i))) //n是数组的长度{C[i] += val;}
}
//也可写成while

这个(i & (-i)) 就是lowbit(i),
lowbit(i)的意思是将i转换为二进制后，保留最低位的1和后面的0，删去前面的数，再转换为十进制后的值。
比如
7的二进制是111，lowbit(7) = 1;
6的二进制是110，lowbit(6) = 2;

如果我要更新A[1]，i = 1, 那么除了C[1]会变成新的值,
lowbit(1) = 1, i += lowbit(1) = 2, C[i] = C[2] 会被更新，
lowbit(i) = lowbit(2) = 2, i += lowbit(2) = 4, C[i] = C[4] 会被更新，
lowbit(i) = lowbit(4) = 4, i += lowbit(4) = 8, C[i] = C[8] 会被更新
……

如果要更新A[3], i = 3, 那么处理C[3]会更新，
lowbit(3) = 1, i += lowbit(3) = 4, C[4] 会被更新，
lowbit(4) = 4, i += lowbit(4) = 8, C[8] 会被更新，
……

再看查询：
比如求前7个数的和query(7),
$7 = 2^2 + 2^1 + 2^0 = 4 + 2 + 1$ ,那么就把前7个数分成三段，
每一段的长度分别为4， 2， 1，即区间[1, 4]，区间[5, 6]和区间[7,7]。
query(7) = getSum(1, 4) + getSum(5, 6) + getSum(7, 7) ,也就是C[4]+C[6]+C[7]，所以计算前7个数的和的时候，只要计算C[4] + C[6] + C[7] 就好了。

再比如求前8个数的和query(8),
$8 = 2^3$ ，那么就把前8个数分成1段，长为8，
query(8) = getSum(1,8),也就是C[8]。

这时反过来对着图你会发现C[8]就是前8个数的和，C[4]就是区间[1, 4] 的和……

可是在计算时我们怎么找到，怎么直接得到C[4],C[6]的值呢？
这里还是要用lowbit,其实lowbit求的就是这些宽度。

int query(int i) //查询前i个数的和
{int ans = 0; for( ; i ; i -= (i & (-i))) ans += C[i]; return ans; 
}
//也可写成while

至于区间查询

int getSum(int i, int j)
{return query(j) - query(i - 1); 
}

一道模板题
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1166
code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e4 + 7;
int T, N;
int a[MAXN], c[MAXN];
int lowbit(int x)
{return x&(-x);
}
void upData(int i, int val)
{while(i <= N){c[i] += val;i += lowbit(i);}
}
int Query(int i)
{int ans = 0;while(i > 0){ans += c[i];i -= lowbit(i);}return ans;
}int main()
{scanf("%d", &T);for(int Case = 1; Case <= T; Case++){printf("Case %d:\n", Case);scanf("%d", &N);memset(a, 0, sizeof(a));memset(c, 0, sizeof(c));for(int i = 1; i <= N; i++){scanf("%d", &a[i]);upData(i, a[i]);}char s[10];while(~scanf("%s", s)){if(s[0] == 'E') break;int a, b;scanf("%d %d", &a, &b);if(s[0] == 'Q'){printf("%d\n", Query(b) - Query(a - 1));}else if(s[0] == 'A'){upData(a, b);}else if(s[0] == 'S'){upData(a, -b);}}}return 0;
}