树状数组
树状数组
1. 绪论
树状数组本质上是一个 运用了 分块思想 的 前缀和 数组，使得查询和修改的时间复杂度都是\(O(logN)\) 级别，但由于是一个前缀和数组，所以对于一些区间能做的事情还是十分有限，鉴于树状数组的实现简单，代码量少，对于问题是否使用树状数组还是线段树的情况需要自行辨别
2. 模板
#define lowbit(a) a&(-a)
int Trarr[100005];
void add(int x, int val){
while(x <= MAX_LIMIT){
Trarr[x] += val;
x += lowbit(x);
}
}
int getsum(int x){
int ans = 0;
while(x){
ans += Trarr[x];
x -= lowbit(x);
}
return ans;
}
3. 经典模型
-
PUIQ问题 (单点修改及区间求和) \(OptA\) . \(a_i += P\) \(OptB\) . \(\sum^i_{[L,R]} a_i\)
考虑点 \(i\) 的值发生变化时会影响到树状数组的哪些部分，然后进行更新就可以了，一般是在点 \(i\) 加一个负值去消除原数的影响再加入新数，并更新其前继数组，区间求和就和前缀和一样，直接 \(getsum(R) – getsum(L-1)\)
见 Luogu P3374
-
IUPQ问题 (区间修改和单点查询) \(Opt\) \(a_i += P,\quad i\in[L, R]\) \(Quiry\quad a_[i]\)
考虑结合差分算法，区间修改是差分的算法优势，对于单点求值就是差分的前缀和，此时用树状数组来维护差分的前缀和数组就可以解决，对于区间修改直接\(Add(L, V)\quad Add(R+1, -V)\) 单点求和就相当于查前缀和数组 不再赘述
见 Luogu P3368
-
求逆序数问题 \(Count \quad i < j , a_i > a_j\) 如 $1,5,2,4,3 $ 中的\((5,2)\)是一对逆序对
核心思想是记录 在树状数组中记录值为 \([1,a_i]\) 的个数，注意不是单纯的将数据的值作为树状数组的下标，将树状数组当一个桶用，树状数组本质是一个前缀和数组，这样是行不通的，此时的\(Add(a_i, 1)\) 操作就是记录值在\([1,a_i]\) 的数又多一个, 计算逆序数时就一边遍历，一边将当前的数计入树状数组，然后询问比自己小的数有多少个 即询问值在\([1, a_i]\)的数有多少个，此时得到的是 \(i < j, ai < aj\) 的数，再用当前的 \(i\) 减去这个值就能得到这个位置的逆序数
见 Luogu P1966
统计个数的思想十分常用，有时也将树状数组数组全初始化为1或0，来查找第k个此时的值，结合下面的二分
-
二分思想 就是在查找的过程中进行二分枚举
比如你每次可以往容器中丢入一个编号为 \(i\) 的球，或者询问容器中编号第 \(K\) 大的球的编号，显然对于编号第 \(K\) 的球，前面只能有 \(K-1\) 个球比他大， 那就有\(getsum(N) – getsum(x) <= K-1\) ，同时由于前缀和的特殊性，树状数组中可能存在多个该情况的数字，此时取第一个数字，由于前缀和必然满足单调性，所以此时可以使用二分来查找满足这个条件的数字
-
区间排序思想 有时为了维护区间或者比较多个区间内的信息，会固定一端进行排序
如给定 \(N\) 个区间，计算第 \(i\) 个区间有多少个区间大于他，此时可以将给定的区间按右端点从大到小排序，右端点相同的则左端点小的排前面，用树状数组维护左端点的插值，即读入第 \(i\) 个区间时，就进行 \(Add(L_i, 1)\)，表示\([1,L_i]\) 这一段中又插入了一个区间，查询时直接询问这一段有多少个区间就可以，因为我们进行了排序，所以保证右端点是递减的。
还有如给定长度为 \(N\) 的一个序列，有 \(Q\) 个询问对于某段区间内的数字有多少种，此时也可进行区间排序，然后一边遍历一边维护，考虑对于第二次出现的数字，在树状数组中消除他在第一次出现的影响，并在第二次出现的位置更新它，即我们此时在树状数组中维护的信息是 \([1, R]\)中有多少种数，并且保证了出现的数字不重复计算，且始终将其更新到最右端 。
最后计算答案时只要询问 \(getsum(quiry[i].R) – getsum(quiry[i].L-1)\)
见 Luogu P4113
-
多维树状数组 有时一维的树状数组无法维护全部信息，此时选择多维记录状态
如一个 \(N*M\) 的方格，每个格子初始时有一个整数权值，接下来有两种操作:
改变一个格子里权值或者求一个子矩阵中特定权值出现的个数，此时我们选择开一个三维的树状数组，前两维表示位置，第三维表示数字(类逆序数模型)，维护时就用两个for循环去控制位置，然后再对应数字位置上\(+val\) 如下面代码
#define lowbit(a) a&(-a) void Tradd(int x, int y, int val, int color){ for(int i = x; i <= N; i += lowbit(i)){ for(int j = y; j <= M; j += lowbit(j)){ Trarr[i][j][color] += val; } } } int Trqui(int x, int y, int color){ int ans = 0; for(int i = x; i; i -= lowbit(i)){ for(int j = y; j; j -= lowbit(j)){ ans += Trarr[i][j][color]; } } return ans; }
询问的时候就类似二维前缀和
\(Trqui(x2, y2, color) – Trqui(x1-1, y2, color) – Trqui(x2, y1-1, color) + Trqui(x1-1, y1-1, color)\)
不明白的读者可以尝试画一个图就能明白
这题见Luogu P4054
4. 大应用题
这里提供一道比较麻烦的例题 Luogu P3960
大概的一个思路每行单独维护，因为互不影响，最后一列比较特殊也需要单独维护，然后离线问题，将问题按照行从小到大排列，然后预处理每列的真实删除位置，比如对于\((1,3)\) 是删除第一行第三列数字，第二次删除时就不再是\((1,3)\) 了，考虑其先向左对齐，所以下一个删除的数字就是\((1,4)\)，我们的预处理就是要找出这个\(4\)
这个预处理运用的是一个逆序数模型和二分模型，对于每一个删除的数字，要通过树状数组去预处理，确认这个数字真实的删除位置，维护这个信息需要将树状数组全部初始化成\(1\)，查找需要删除的数字时，就二分查找值等于题目指定删除数字的列数，删除后\(Add(x, -1)\)
然后将问题按照问的顺序重新恢复，在进行模拟，对于真实位置小于列数的情况直接删除就可以，等于列数的情况就直接在最后一列上动手脚，大于列数的情况就额外开一个Vector数组去存每行每列额外的数字，这个最后一列删除的情况也是运用二分+树状数组去处理实际删除的是第几行 然后就AC了
下面是AC代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
#include <vector>
#define int long long
#define lowbit(a) a&(-a)
using namespace std;
const int maxn = 1e5+5;
int N, M, Q, Tr1[600005], Tr2[600005], last[600005];
vector<int> Extra[300005];
struct info{
int x, y, pos;
bool vis;
};
struct info quiry[300005];
void Tr1add(int x, int val){
while(x <= 600005){
Tr1[x] += val;
x += lowbit(x);
}
}
int Tr1qui(int x){
int ans = 0;
while(x){
ans += Tr1[x];
x -= lowbit(x);
}
return ans;
}
void Tr2add(int x, int val){
while(x <= 600005){
Tr2[x] += val;
x += lowbit(x);
}
}
int Tr2qui(int x){
int ans = 0;
while(x){
ans += Tr2[x];
x -= lowbit(x);
}
return ans;
}
bool cmp1(info a, info b){
if(a.x == b.x) return a.pos < b.pos;
else return a.x < b.x;
}
bool cmp2(info a, info b){
return a.pos < b.pos;
}
signed main(){
clock_t c1 = clock();
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%lld%lld%lld", &N, &M, &Q);
for(int i = 1; i <= Q; i++){
scanf("%lld%lld", &quiry[i].x, &quiry[i].y);
quiry[i].pos = i;
}
for(int i = 1; i <= 600005; i++) Tr1add(i, 1), Tr2add(i, 1);
for(int i = 1; i <= N; i++){
last[i] = i*M;
}
sort(quiry+1, quiry+1+Q, cmp1);
int Now = 1;
for(int i = 1; i <= Q; i++){
int Len = M;
while(Now < Q && quiry[i].x == quiry[Now+1].x) Now++;
vector<int> mid;
for(int j = i; j <= Now; j++){
if(quiry[j].y == M){
quiry[j].vis = true;
continue;
}
int L = 1, R = Len;
while(R > L){
int MID = (R+L) / 2;
if(Tr1qui(MID) >= quiry[j].y) R = MID;
else L = MID+1;
}
mid.push_back(L); Tr1add(L, -1); Len++; quiry[j].y = L;
}
for(int j = 0; j < mid.size(); j++) Tr1add(mid[j], 1);
i = Now;
}
sort(quiry+1, quiry+1+Q, cmp2);
int Len = N;
for(int i = 1; i <= Q; i++){
int ans;
if(!quiry[i].vis){
if(quiry[i].y < M) ans = (quiry[i].x-1)*M+quiry[i].y, printf("%lld\n", ans);
else{
quiry[i].y -= M; ans = Extra[quiry[i].x][quiry[i].y];
printf("%lld\n", ans);
}
}
int L = 1, R = Len;
while(R > L){
int MID = (R+L) / 2;
if(Tr2qui(MID) >= quiry[i].x) R = MID;
else L = MID+1;
}
Tr2add(L, -1);
if(quiry[i].vis) ans = last[L], printf("%lld\n", ans);
else Extra[quiry[i].x].push_back(last[L]);
last[++Len] = ans;
}
end:
cerr << "Time Used: " << clock() - c1 << "ms" << endl;
return 0;
}
