树状数组
什么是树状数组（一把锋利的手术刀）
引入问题
给出一个长度为n的数列，完成以下两种操作
- 将数列中的第x个数加上d
- 求出 [l,r] 这一区间的区间和
看到操作一时，你轻蔑一笑，这直接在给出的数列上改不就行了，那么好，接下来看操作二，你又轻蔑一笑，这不就是之前学的前缀和嘛，这有什么难的？
那你有没有想过，你心中的操作一的时间复杂度为O(1)，操作二的时间复杂度为O(n)，当n达到千万级别时，这种复杂度是我们不能接受的。
这时，作为一名专业抬杠运动员的你不太服气，你说要在输入的时候直接维护前缀和数组，放弃维护给出的数列，这样操作二的时间复杂度就直线下降为O(1),那返回去看操作一的时间复杂度呢？此时我们是不知道每一位上的数是多少的，可以通过前缀和数组倒着推出原数列（时间复杂度O(n)），修改完原数列（时间复杂度O(1)）之后再求一遍前缀和（时间复杂度O(n)），看到这，你自己也知道这行不通。
不出意料，你又又又抬杠，你说为什么非要只维护一个数组呢？我在输入的时候维护两个数组，一个原数列，一个前缀和数组，这样不行吗？
显然这是不对的，当你对原数列做出修改时，之前维护好的前缀和数组已经不是更改后的数列的前缀合数组了。
这时，我告诉你，有一种方法可以使两个操作的时间复杂度均为O(logn2),这样即使n为千万级别，时间复杂度也只有十几而已，听到这你肥肠鸡冻，迫不及待的往下学习。（不激动的可以点XX退出了hh）
观看此视频 → 什么是树状数组 想必什么是树状数组也不必再多说什么。
明白什么是树状数组后，我们来看看树状数组的基础操作
lowbit()函数
//返回x的最后一位1的大小
int lowbit(int x)
{
return x & - x;
}
单点修改
void add(int x,int c)
{
for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}
区间查询
int sum(int x)
{
int res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
了解树状数组的基础操作之后，我们可以来完成下面这道题
1. 逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；
否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
数列中的元素的取值范围 [1,109]
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路
1. 对于原数组中的每一个数，与其构成逆序对的是下标比它小且数值比它大的元素，那么我们用一个额外数组b[],
b[i]表示原数组a[]中 i 出现的次数，b[i]的前缀和sum(i)为 <= b[i] 的数的总个数，那么sum(n) - sum(i)
即为 > b[i] 的数的总个数，要求逆序对的数量还需满足：这些 > b[i] 的数是在b[i]之前的，那如何保证
sum(n) - sum(i)是表示在b[i]之前且 > b[i] 的数的总个数呢？答案是边做变更新b[]数组，顺序遍历原数组，
当遍历到a[i]时，先求出与a[i]构成的逆序对的数量，再将b[a[i]] + 1。
对于b[]数组，可以用树状数组tr[]代替，tr[i]表示大小在[i - lowbit(i) + 1 , i]这一区间内的数的总个数。
2. 还需要注意一下数据范围，原数组的总长度在 10 ^ 6 以内，而每个数的大小却在 10 ^ 9 以内，树状数组的
长度取决于原数组中的最大值，举个例子，如果输入样例为：1 5 99，数据只有3个数，而我们需要开长度为99的
数组，这显然很不划算，所以还需对原数组进行离散化。
离散化的操作为：排序 + 判重 + 二分（至于为什么是这样，请读者自学，这里就不详细解释了hh）
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 100010;
int n,idx;
int a[N],tr[N];
vector<int> alls;
int find(int x)
{
int l = 1,r = alls.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int lowbit(int x)
{
return x & - x;
}
void add(int x,int c)
{
for( int i = x ; i <= alls.size() - 1 ; i += lowbit(i) ) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
int main()
{
alls.push_back(0);
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
{
scanf("%d",&a[i]);
alls.push_back(a[i]);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
long long res = 0;
for( int i = 1 ; i <= n ; i ++ )
{
int k = find(a[i]);
res += sum(alls.size() - 1) - sum(k);
add(k,1);
}
printf("%lld",res);
return 0;
}
有了上一道题的基础，下面这道题可谓是轻而易举！
2. 楼兰图腾
在完成了分配任务之后，西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜
铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水
平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为
(1,y1),(2,y2),…,(n,yn)，其中y1∼yn是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点(i,yi),(j,yj),(k,yk)满足 1≤i<j<k≤n 且 yi>yj,yj<yk，则称这三个点
构成 V 图腾;
如果三个点(i,yi),(j,yj),(k,yk)满足 1≤i<j<k≤n 且 yi<yj,yj>yk，则称这三个点
构成 ∧ 图腾;
西部 314 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个数 n。
第二行是 n 个数，分别代表 y1，y2,…,yn。
输出格式
两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。
数据范围
对于所有数据，n≤200000，且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。
输入样例：
5
1 5 3 2 4
输出样例：
3 4
思路
1. 以∧ 为例，我们假设 a[i] 为最高点，它与在 [1,i-1] 和 [i+1,n] 这两个区间中比 a[i] 小的点构成 ∧ 图
案，也就是说我们需要求出这两个区间中比 a[i] 小的数的总个数，将其相乘得到 ∧ 图案的数量。
2. 我们可以用朴素方法，每求一个 small[i] 都按顺序遍历一次，求出符合要求的点的个数，也可以换一种思路，用
一个数组 c[i] 表示 i 出现的个数，顺序遍历原数组，每求一个 small[i] 就是求 c[i-1] 的前缀和，顺便
将c[i]更新。这两种方法，显而易见选择第二种，因为前缀和问题可以用树状数组来进行优化。
3. 定义 tr[] 数组，tr[i] 表示：原数组 a[] 中大小在 [i - lowbit(i) + 1 , i] 这一区间内出现的个数。
也就是第二点中 c[] 数组在 [i - lowbit(i) + 1 , i] 这一区间的区间和
4. 二维偏序问题，我们可以思考是否可以用树状数组来解决。(逆序对就是二维偏序的一种)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
typedef long long LL;
int n;
int a[N];//原输入数组
int tr[N];//树状数组，本题中 tr[i] 表示 [i - lowbit(i) + 1 , i] 这一区间内的数出现的总个数
int big[N],small[N];//big[i]数组表示在a[i]前比a[i]大的数的总个数
//small[i]数组表示在a[i]前比a[i]小的数的总个数
int lowbit(int x)
{
return x & - x;
}
void add(int x,int c)
{
for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);//由树状数组原理知，下标不能从 0 开始
for( int i = 1 ; i <= n ; i ++ )
{
big[i] = sum(n) - sum(a[i]);
small[i] = sum(a[i] - 1);
add(a[i],1);
}//以 V 为例，由前往后遍历，得出在a[i]前边且比a[i]大的数的总个数
memset(tr,0,sizeof tr);
LL res1 = 0,res2 = 0;//以数量最多的情况为例，i在正中间这一类，左边最多n/2个，右边最多也n/2个
//那么这一类就有n方个，共有n类，极限就是n的3次方（当然一定不会这么大）
//所以开成 long long 类型万无一失
//由后往前遍历，得出在a[i]后边且比a[i]大的数的总个数，这里边做边乘即可，不需要再将其存储下来
for( int i = n ; i ; i -- )
{
res1 += big[i] * (LL)(sum(n) - sum(a[i]));
res2 += small[i] * (LL)(sum(a[i] - 1));
add(a[i],1);
}
printf("%lld %lld",res1,res2);
return 0;
}
经历了前两题的历练，我们来挑战一下树状数组的拓展
3. 一个简单的整数问题
题目描述
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105
|d|≤10000
|A[i]|≤109
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例：
4
1
2
5
思路
1. 树状数组的基础操作是单点修改和区间查询，而本题的两个操作恰恰相反，是区间修改和单点查询，怎么解决？
当然用差分操作，我们知道差分数组b[i] + d，会使原数组a[i]及a[i]之后的数全部 + d，且b[i]的前缀和正好
也是a[i]，与题目要求完全合拍。
2. 无论是原数组还是差分数组，本质都是单点修改和区间查询，只是操作的对象不同，从而使产生的效果不同。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m;
int a[N];
LL tr[N];
int lowbit(int x)
{
return x & - x;
}
void add(int x,int c)
{
for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}
LL sum(int x)
{
LL res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);
for( int i = 1 ; i <= n ; i ++ ) add(i,a[i] - a[i-1]);
while( m -- )
{
char op[5];
scanf("%s",op);
if(op[0] == 'C')
{
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
add(l,d);
add(r+1,-d);
}
else
{
int x;
scanf("%d",&x);
printf("%lld\n",sum(x));
}
}
return 0;
}
再来一道
4. 一个简单的整数问题2
题目描述
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105
|d|≤10000
|A[i]|≤109
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例：
4
55
9
15
思路
1. 两个操作分别是区间修改和区间查询，那么问题在于，我们用树状数组维护原数组还是原数组的差分数组。
2. 如果维护原数组，那么第二个操作的时间复杂度是O(logn)，但第一个操作的时间复杂度是O(n)，也就是说，
总体上的时间复杂度为O(n)。
3. 如果维护原数组的差分数组，那么第一个操作的时间复杂度为O(logn)，再来看第二个操作:求数列 l ~ r 的
区间和，即求原数组的前缀和再进行相减操作。注意：树状数组维护的是差分数组，求 原数组 前缀和！
eg：求x的前缀和
a1 + a2 + a3 + …… + ax
--> b1 + b1 + b2 + b1 + b2 + b3 + …… + b1 + b2 + …… + bx
这样不太方便看，我们把它变成下面这样
b1 |b1 b2 b3 …… bx
b1 b2 b1 |b2 b3 …… bx
b1 b2 b3 补全--> b1 b2 |b3 …… bx | 的后面是补全的
…… ……
b1 b2 b3 …… bx b1 b2 b3 …… bx
我们观察补全之后的（竖着观察），发现这其实也是某个数列的前缀和（i * bi），那么再用一个额外数组维护
这个数列的前缀和即可。
综上，求x的前缀和为 (x + 1) * sum(tr1[] , x) - sum(tr2[] , x - 1)
那么，求 l ~ r 的区间和为 SUM(r) - SUM(l-1)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n,m;
int a[N];
LL tr1[N];//维护原数组 a[i] 的差分数组 b[i] 的前缀和
LL tr2[N];//维护原数组 a[i] 的差分数组 b[i] * i 的前缀和
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[],int x,LL c)
{
for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}
LL sum(LL tr[],int x)
{
LL res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
LL SUM(int x)
{
return sum(tr1,x) * (x + 1) - sum(tr2,x);
}
int main()
{
scanf("%d%d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[i]);
for( int i = 1 ; i <= n ; i ++ )
{
int b = a[i] - a[i-1];
add(tr1,i,b);
add(tr2,i,(LL)i * b);
}
while( m -- )
{
char op[2];
scanf("%s",op);
if(op[0] == 'C')
{
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
add(tr1,l,d);add(tr1,r + 1,-d);
add(tr2,l,l * d);add(tr2,r + 1,(r + 1) * -d);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",SUM(r) - SUM(l-1));
}
}
return 0;
}
来看最后一题
5. 谜一样的牛
题目描述
有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。
输入格式
第 1 行：输入整数 n。
第 2..n 行：每行输入一个整数 Ai，第 i 行表示第 i 头牛前面有 Ai 头牛比它低。
（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）
输出格式
输出包含 n 行，每行输出一个整数表示牛的身高。
第 i 行输出第 i 头牛的身高。
数据范围
1≤n≤105
输入样例：
5
1
2
1
0
输出样例：
2
4
5
3
1
思路
1. 正难则反
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
return x & - x;
}
void add(int x,int c)
{
for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for( int i = x ; i ; i -= lowbit(i) ) res += tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for( int i = 2 ; i <= n ; i ++ ) scanf("%d",&h[i]);
for( int i = 1 ; i <= n ; i ++ ) tr[i] = lowbit(i);
for( int i = n ; i ; i -- )
{
int k = h[i] + 1;
int l = 1,r = n;
while(l < r)
{
int mid = l + r >> 1;
if(sum(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = r;
add(r,-1);
}
for( int i = 1 ; i <= n ; i ++ ) printf("%d\n",ans[i]);
return 0;
}
