树状数组
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 iin[L, R]) (Quiryquad 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("%lldn", ans); else{ quiry[i].y -= M; ans = Extra[quiry[i].x][quiry[i].y]; printf("%lldn", 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("%lldn", ans); else Extra[quiry[i].x].push_back(last[L]); last[++Len] = ans; } end: cerr << "Time Used: " << clock() - c1 << "ms" << endl; return 0; } 
