1、acwing 241 楼兰图腾 树状数组-基础题
题面：相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 ( 1 , y 1 ) , ( 2 , y 2 ) , … , ( n , y n ) ( 1 , y 1 ) , ( 2 , y 2 ) , … , ( n , y n ) ， 其 中 y 1 ∼ y n 是 1 到 n 的 一 个 排 列 (1,y1),(2,y2),…,(n,yn)(1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列 (1,y1),(2,y2),…,(n,yn)(1,y1),(2,y2),…,(n,yn)，其中y1∼yn是1到n的一个排列。
西部 打算研究这幅壁画中包含着多少个图腾。
如果三个点$ (i,y_i),(j,y_j),(k,y_k)$满足
1
≤
i
<
j
<
k
≤
n
1≤i<j<k≤n
1≤i<j<k≤n 且
y
i
>
y
j
,
y
j
<
y
k
y_i>y_j,y_j<y_k
yi>yj,yj<yk，则称这三个点构成 V 图腾;
如果三个点 $ (i,y_i),(j,y_j),(k,y_k)$满足
1
≤
i
<
j
<
k
≤
n
且
y
i
<
y
j
,
y
j
>
y
k
1≤i<j<k≤n 且 y_i<y_j,y_j>y_k
1≤i<j<k≤n且yi<yj,yj>yk，则称这三个点构成 ∧ 图腾;
西部 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
解法： y i y_i yi 取值范围是1到 n的区间，事实上是求每一个点左右两边比他高的有几个，矮的有几个
相乘即可得到答案
关键在于如何求每一个点左右两边比他大或小的数的个数
普通做法O(n^2)
树状数组O(nlogn)
思路：从左往右遍历，一个个添加到树状数组中，随即查询比他小的数的个数即可
AC代码：
ll lowbit(ll x){
return x & (-x);
}
ll add(ll x, ll val){ //单点增加
for(int i=x; i<=n; i+=lowbit(i)){
tree[i] += val;
}
}
ll query(ll x){
ll res = 0;
for(int i=x; i>=1; i-=lowbit(i) ){
res += tree[i];
}
return res;
}
ll sum(ll l, ll r){
if(l > r) return 0;
return query(r) - query(l-1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>y[i];
//从左往右：
memset(tree, 0, sizeof(tree));
for(int i=1;i<=n;i++){
left_larger[i] = sum(y[i] + 1, n);
left_lower[i] = sum(1, y[i] - 1);
add(y[i] , 1);
}
}
2、acwing 242 树状数组 + 差分
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加上 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
区间修改 + 单点查询：与树状数组要求正好相反！
基于差分的思想：
差分数组： c [ i ] = a [ i ] − a [ i − 1 ] c[i] = a[i] - a[i-1] c[i]=a[i]−a[i−1]
有： a [ k ] = ∑ i = 1 k c [ i ] a[k] = \sum_{i=1}^{k}c[i] a[k]=∑i=1kc[i]
让原数组a[i] 在 L~R 区间加上 d，即 c [ L ] + d , c [ R + 1 ] − d c[L]+d , c[R+1] - d c[L]+d,c[R+1]−d
因此：原数组的单点查询 变成了 差分数组的区间查询
原数组的区间修改 转化成了 差分数组的两个单点修改操作
-
注意：差分数组的初始化：
-
c[i] = a[i] - a[i-1]; for(int i=1;i<=n;i++){ add(i, c[i]); }
3、acwing 244谜一样的牛 树状数组 + 二分搜索
有 n 头奶牛，已知它们的身高为 1∼n且各不相同，但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。
输入样例：
5
0 1 2 1 0
输出样例：
2
0 4 5 3 1
思路 + 分析：
- 从后往前看，可以得知具体身高 = 第 x + 1 矮的（从1~n未选过的里面）
- 设置一个全为 1 的一维数组，若第x项被选了，则前缀和 = x + 1的坐标位置即为所求
- 例如：1 0 1 1 0 0 1
- 前缀和 1 1 2 3 3 3 4
- 第3矮的位置是4号，因此具体身高为 4 ，所以所求为前缀和第一个值为3的位置—二分
AC代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110000;
int n,a[N];
int bit[N], tree[N], c[N];
int lowbit(int x){
return x & (-x);
}
int add(int x, int val){
for(int i=x; i<=n; i+=lowbit(i)){
tree[i] += val;
}
}
int query(int x){
int res = 0;
for(int i=x;i>=1; i-=lowbit(i)){
res += tree[i];
}
return res;
}
int main(){
cin>>n;
for(int i=2;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
bit[i] = 1;
add(i , 1);
}
for(int i=n; i>=1; i--){
int x = a[i] + 1;
//二分查询bit数组前缀和为 x的第一个位置
int l=1,r=n,mid, ans = 0;
while(l<=r){
mid = (l+r)/2;
if(query(mid) >= x){
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
add(ans, -1);
c[i] = ans;
}
for(int i=1;i<=n;i++){
cout<<c[i]<<endl;
}
return 0;
}