Fenwick Tree, (also known as Binary Indexed Tree，二叉索引树), is a high-performance data structure to calculate the sum of elements from the beginning to the indexed in a array.
It needs three functions and an array:
- Array sum; It stores the data of Fenwick Tree.
- int lowbit(int); To get the last 1 of the binary number. 取出最低位 1
- void modify(int, int); To modify the value of an element, the second input "val" is the value that would be added.
- int query(int); To get the sum of elements from the beginning to the indexed.
How to get the last 1 of a binary number? Use AND operating: x & (-x).
Definitions:
int sum[N]; inline int lowbit(int x) { return x & (-x); } inline void modify(int x, int val) { while (x <= n) { d[x] += val; x += lowbit(x); } } inline int query(int x) { int sum = 0; while (x > 0) { sum += d[x]; x -= lowbit(x); } return sum; }
例题1：洛谷P3374 【模板】树状数组 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x k 含义：将第x个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：输出包含若干行整数，即为所有操作2的结果。
代码：
1 /* P3374 【模板】树状数组 1 2 * Au: GG 3 */ 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cmath> 8 #include <ctime> 9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12 const int N = 500000 + 3; 13 int n, m, d[N]; 14 15 inline int lowbit(int x) { 16 return x & (-x); 17 } 18 inline void modify(int x, int val) { 19 while (x <= n) { 20 d[x] += val; x += lowbit(x); 21 } 22 } 23 inline int getsum(int x) { 24 int sum = 0; 25 while (x > 0) { 26 sum += d[x]; x -= lowbit(x); 27 } 28 return sum; 29 } 30 31 int main() { 32 scanf("%d%d", &n, &m); 33 for (int i = 1, w; i <= n; i++) { 34 scanf("%d", &w); modify(i, w); 35 } 36 while (m--) { 37 int o, x, y; 38 scanf("%d%d%d", &o, &x, &y); 39 if (o == 1) modify(x, y); 40 if (o == 2) printf("%d ", getsum(y) - getsum(x - 1)); 41 } 42 return 0; 43 }
例题2：洛谷P3368 【模板】树状数组 2
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的和
输入输出格式
输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x 含义：输出第x个数的值
输出格式：输出包含若干行整数，即为所有操作2的结果。
数据直接 modify 到差分数组里，方便区间修改和单元素查询（原本树状数组作用是方便单元素修改和区间查询 
）。
代码：
1 /* P3368 【模板】树状数组 2 2 * Au: GG 3 */ 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cmath> 8 #include <ctime> 9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12 const int N = 500000 + 3; 13 int n, m, d[N]; 14 15 inline int lowbit(int x) { 16 return x & (-x); 17 } 18 inline void modify(int x, int val) { 19 while (x <= n) { 20 d[x] += val; x += lowbit(x); 21 } 22 } 23 inline int getsum(int x) { 24 int sum = 0; 25 while (x > 0) { 26 sum += d[x]; x -= lowbit(x); 27 } 28 return sum; 29 } 30 31 int main() { 32 scanf("%d%d", &n, &m); 33 for (int i = 1, w, v = 0; i <= n; i++) { 34 scanf("%d", &w); modify(i, w - v); v = w; 35 } 36 while (m--) { 37 int o, x, y, k; 38 scanf("%d%d", &o, &x); 39 if (o == 1) { 40 scanf("%d%d", &y, &k); 41 modify(x, k); modify(y + 1, -k); 42 } 43 if (o == 2) printf("%d ", getsum(x)); 44 } 45 return 0; 46 }