树状数组是什么？如何高效处理数据查询？

本文共计2603个文字，预计阅读时间需要11分钟。

树状数组的优势在于其前缀和及数组操作的时间复杂度均为\(O(\log N)\)级别，适用于查询和修改。但因为它是一个前缀和及数组，所以在一些区间操作上仍有限制。

树状数组 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; }