树状数组

给出一个长度为nn的数组，完成以下两种操作：
1. 将第ii个数加上kk
2. 输出区间[i,j][i,j]内每个数的和

朴素算法
单点修改：O(1)O(1)
区间查询：O(n)O(n)
使用树状数组
单点修改：O(logn)O(logn)
区间查询：O(logn)O(logn)
前置知识
lowbit()lowbit()运算：非负整数xx在二进制表示下最低位1及其后面的0构成的数值。

举例说明：
lowbit(12)=lowbit([1100]2)=[100]2=4

树状数组思想
树状数组的本质思想是使用树结构维护”前缀和”，从而把时间复杂度降为O(logn)O(logn)。

对于一个序列，对其建立如下树形结构：

每个结点t[x]保存以x为根的子树中叶结点值的和
每个结点覆盖的长度为lowbit(x)
t[x]结点的父结点为t[x + lowbit(x)]
树的深度为log2n+1

add(x, k)表示将序列中第x个数加上k。

以add(3, 5)为例：
在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确。时间复杂度为O(logn)O(logn)。
void add(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
t[i] += k;
}
ask(x)表示将查询序列前x个数的和

以ask(7)为例：
查询这个点的前缀和，需要从这个点向左上找到上一个结点，将加上其结点的值。向左上找到上一个结点，只需要将下标 x -= lowbit(x)，例如 7 - lowbit(7) = 6。
int ask(int x)
{
int sum = 0;
for(int i = x; i; i -= lowbit(i))
sum += t[i];
return sum;
}

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int N = 2000010;
 8 
 9 typedef long long LL;
10 
11 int n;
12 //t[i]表示树状数组i结点覆盖的范围和
13 int a[N], t[N];
14 //Lower[i]表示左边比第i个位置小的数的个数
15 //Greater[i]表示左边比第i个位置大的数的个数
16 int Lower[N], Greater[N];
17 
18 //返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
19 int lowbit(int x)
20 {
21     return x & -x;
22 }
23 
24 //将序列中第x个数加上k。
25 void add(int x, int k)
26 {
27     for(int i = x; i <= n; i += lowbit(i)) t[i] += k;
28 }
29 //查询序列前x个数的和
30 int ask(int x)
31 {
32     int sum = 0;
33     for(int i = x; i; i -= lowbit(i)) sum += t[i];
34     return sum;
35 }
36 
37 int main()
38 {
39 
40     scanf("%d", &n);
41     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
42 
43     //从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
44     for(int i = 1; i <= n; i++)
45     {
46         int y = a[i]; //第i个数
47 
48         //在前面已加入树状数组的所有数中统计在区间[1, y - 1]的数字的出现次数
49         Lower[i] = ask(y - 1); 
50 
51         //在前面已加入树状数组的所有数中统计在区间[y + 1, n]的数字的出现次数
52         Greater[i] = ask(n) - ask(y);
53 
54         //将y加入树状数组，即数字y出现1次
55         add(y, 1);
56     }
57 
58     //清空树状数组，从右往左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
59     memset(t, 0, sizeof t);
60 
61     LL resA = 0, resV = 0;
62     //从右往左统计
63     for(int i = n; i >= 1; i--)
64     {
65         int y = a[i];
66         resA += (LL)Lower[i] * ask(y - 1);
67         resV += (LL)Greater[i] * (ask(n) - ask(y));
68 
69         //将y加入树状数组，即数字y出现1次
70         add(y, 1);
71     }
72 
73     printf("%lld %lld\n", resV, resA);
74 
75     return 0;
76 }