浅谈如何用块状数组高效实现加强版普通平衡树
xingtiankai2023 · · 算法·理论
前言
自古以来我们就有多种实现普通平衡树的方法,但大多要么实现复杂,要么效率堪忧。本文介绍了一种兼具高效性和实操性的树状数组 + 块状数组的解法。
一:整体思路
将元素按从小到大分成若干个块,块内初始有
二:核心变量
pool:槽位,用于存储数据。bid:每个块所属的槽位。sz:当前块大小。mx:块内最大值。fw:树状数组。ns:已经分配的槽位的数量。nb:当前块的个数。tot:当前元素的个数。三:实现
预处理
添加值为
-\infty 和\infty 的哨兵(防止块被删完)。
将初始值排序后按每B 个分成一个块,然后建树状数组。前置操作
find_block:查找第一个最大值
\ge x 的块lower_bound或倍增,实测倍增总时长快 60ms。 :::info[代码(lower_bound)]inline int find_block(int x) { // 找第一个mx>=x的块 return lower_bound(mx + 1,mx + nb + 1,x) - mx; }::: :::info[代码(倍增)]
inline int find_block(int x) { // 找第一个mx>=x的块 int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { if (i + pw <= nb && mx[i + pw] < x) { i += pw; } } return i + 1; }:::
find_pos:查找块
i 中第一个\ge x 的位置lower_bound或10 步一跳,实测10 步一跳总时长快 120ms。 :::info[代码(lower_bound)]inline int find_pos(int i,int x) { // 找到块内第一个>=x的位置 int *b = pool[bid[i]]; return lower_bound(b + 1,b + sz[i] + 1,x) - b; }::: :::info[代码(
10 步一跳)]inline int find_pos(int i,int x) { // 找到块内第一个>=x的位置 int *b = pool[bid[i]],j = 1; while (j + 9 <= sz[i] && b[j + 9] < x) j += 10; while (j <= sz[i] && b[j] < x) j++; return j; }:::
split:将块
i 分裂成两个块新开一个块并将后半段复制过去,再重建树状数组。 :::info[代码]
inline void split(int i) { // 分裂第i个块 int h = sz[i] >> 1,m = sz[i] - h; int id = ++ns; memcpy(pool[id] + 1,pool[bid[i]] + h + 1,m * sizeof(int)); for (int j = nb; j > i; j--) { bid[j + 1] = bid[j]; sz[j + 1] = sz[j]; mx[j + 1] = mx[j]; } bid[i + 1] = id; sz[i + 1] = m,mx[i + 1] = pool[id][m]; sz[i] = h,mx[i] = pool[bid[i]][h]; nb++; build_fw(); }:::
remove:删除空块
i 将后面的块整体前移,再重建树状数组。 :::info[代码]
inline void remove(int i) { // 删除第i个块 for (int j = i; j < nb;j++) { bid[j] = bid[j + 1]; sz[j] = sz[j + 1]; mx[j] = mx[j + 1]; } nb--; build_fw(); }:::
build_fw / add_fw / sum_fw:建树状数组,单点加,查询前缀和
同普通的树状数组。 :::info[代码]
inline void build_fw() { // 线性建树状数组 memcpy(fw + 1,sz + 1,nb * sizeof(int)); for (int i = 1; i <= nb; i++) { int j = i + (i & -i); if (j <= nb) fw[j] += fw[i]; } } inline void add_fw(int x,int v) { for (; x <= nb; x += x & -x) fw[x] += v; } inline int sum_fw(int x) { int ans = 0; for (; x; x -= x & -x) ans += fw[x]; return ans; }:::
clear:清空
:::info[代码]
inline void clear() { ns = 1,nb = 1,tot = 2; pool[1][1] = -inf,pool[1][2] = inf; bid[1] = 1,sz[1] = 2,mx[1] = inf; fw[1] = 2; }:::
基本操作
insert:插入
x 找到第一个
mx\ge x 的块,若块已满,则将其分裂,然后将块中后面的元素往后移并插入x 。 :::info[代码]inline void insert(int x) { tot++; int i = find_block(x),p; if (i == nb + 1) i = nb,p = sz[nb] + 1; else p = find_pos(i,x); if (sz[i] == CAP) { split(i); if (p > sz[i]) p -= sz[i],i++; // 分到了右边的块 } int *b = pool[bid[i]]; memmove(b + p + 1,b + p,(sz[i] - p + 1) * sizeof(int)); b[p] = x,sz[i]++,mx[i] = b[sz[i]]; add_fw(i,1); }:::
erase:删除
x 找到第一个
mx\ge x 的块,若块大小为1 ,直接删除块,否则将后面的元素左移并覆盖x 。 :::info[代码]inline void erase(int x) { tot--; int i = find_block(x),p = find_pos(i,x); if (sz[i] == 1) { remove(i); return; } int *b = pool[bid[i]]; memmove(b + p,b + p + 1,(sz[i] - p) * sizeof(int)); sz[i]--,mx[i] = b[sz[i]]; add_fw(i,-1); }:::
get_rank:查询
x 的排名找到
x 所在的块i ,用树状数组查询前i - 1 个块的元素个数,再加上x 在块内的位置。 :::info[代码]inline int get_rank(int x) { int i = find_block(x); if (i == nb + 1) return tot; return sum_fw(i - 1) + find_pos(i,x) - 1; }:::
get_kth:查询第
k 小的元素用树状数组倍增找到第
k 个元素所在的块。 :::info[代码]inline int get_kth(int k) { k++; int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { // 树状数组倍增 if (i + pw <= nb && fw[i + pw] < k) { i += pw; k -= fw[i]; } } return pool[bid[i + 1]][k]; }:::
get_prev:查询前驱
- 若
x 大于全局最大值,则为全局最大值。 - 否则找到第一个
mx\ge x 的块。- 若该块最小值
\ge x ,返回上一个块的最大值。 - 否则用
lower_bound找到小于x 的最大值。 :::info[代码]inline int get_prev(int x) { int i = find_block(x); if (i == nb + 1) return mx[nb]; else if (pool[bid[i]][1] < x) return pool[bid[i]][find_pos(i,x) - 1]; else return mx[i - 1]; }:::
get_next 查询后继
找到第一个
mx\ge x+1 的块,在块内用lower_bound找到第一个\ge x + 1 的元素。
:::info[代码]inline int get_next(int x) { int i = find_block(x + 1); return pool[bid[i]][find_pos(i,x + 1)]; }:::
总代码
:::info[代码(可过 P6136)]
#include<bits/stdc++.h> using namespace std; #define clz __builtin_clz char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) inline int read() { int x=0,f=1;char chr=getchar(); while (chr<'0'||'9'<chr){if(chr=='-')f=-f;chr=getchar();} while ('0'<=chr&&chr<='9'){x=x*10+chr-'0';chr=getchar();} return x*f; } const int N = 1.1e6 + 10; const int BS = 200; // 初始块大小 const int CAP = 2 * BS; // 块容量 const int B = 2 * N / BS + 256; // 总块数 const int inf = 0x7fffffff; int pool[B][CAP + 1]; // 块的数据 int bid[B]; // 第i块所属槽位 int sz[B]; // 块的大小 int mx[B]; // 块内最大值 int fw[B]; // 维护块大小的树状数组 int ns; // 开的块的个数 int nb; // 当前块的个数 int tot; // 当前元素个数 int n,m; int a[N]; inline void build_fw() { // 线性建树状数组 memcpy(fw + 1,sz + 1,nb * sizeof(int)); for (int i = 1; i <= nb; i++) { int j = i + (i & -i); if (j <= nb) fw[j] += fw[i]; } } inline void add_fw(int x,int v) { for (; x <= nb; x += x & -x) fw[x] += v; } inline int sum_fw(int x) { int ans = 0; for (; x; x -= x & -x) ans += fw[x]; return ans; } inline int find_block(int x) { // 找第一个mx>=x的块 int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { if (i + pw <= nb && mx[i + pw] < x) { i += pw; } } return i + 1; } inline int find_pos(int i,int x) { // 找到块内第一个>=x的位置 int *b = pool[bid[i]],j = 1; while (j + 9 <= sz[i] && b[j + 9] < x) j += 10; while (j <= sz[i] && b[j] < x) j++; return j; } inline void split(int i) { // 分裂第i个块 int h = sz[i] >> 1,m = sz[i] - h; int id = ++ns; memcpy(pool[id] + 1,pool[bid[i]] + h + 1,m * sizeof(int)); for (int j = nb; j > i; j--) { bid[j + 1] = bid[j]; sz[j + 1] = sz[j]; mx[j + 1] = mx[j]; } bid[i + 1] = id; sz[i + 1] = m,mx[i + 1] = pool[id][m]; sz[i] = h,mx[i] = pool[bid[i]][h]; nb++; build_fw(); } inline void remove(int i) { // 删除第i个块 for (int j = i; j < nb;j++) { bid[j] = bid[j + 1]; sz[j] = sz[j + 1]; mx[j] = mx[j + 1]; } nb--; build_fw(); } inline void insert(int x) { tot++; int i = find_block(x),p; if (i == nb + 1) i = nb,p = sz[nb] + 1; else p = find_pos(i,x); if (sz[i] == CAP) { split(i); if (p > sz[i]) p -= sz[i],i++; // 分到了右边的块 } int *b = pool[bid[i]]; memmove(b + p + 1,b + p,(sz[i] - p + 1) * sizeof(int)); b[p] = x,sz[i]++,mx[i] = b[sz[i]]; add_fw(i,1); } inline void erase(int x) { tot--; int i = find_block(x),p = find_pos(i,x); if (sz[i] == 1) { remove(i); return; } int *b = pool[bid[i]]; memmove(b + p,b + p + 1,(sz[i] - p) * sizeof(int)); sz[i]--,mx[i] = b[sz[i]]; add_fw(i,-1); } inline int get_rank(int x) { int i = find_block(x); if (i == nb + 1) return tot; return sum_fw(i - 1) + find_pos(i,x) - 1; } inline int get_kth(int k) { k++; int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { // 树状数组倍增 if (i + pw <= nb && fw[i + pw] < k) { i += pw; k -= fw[i]; } } return pool[bid[i + 1]][k]; } inline int get_prev(int x) { int i = find_block(x); if (i == nb + 1) return mx[nb]; else if (pool[bid[i]][1] < x) return pool[bid[i]][find_pos(i,x) - 1]; else return mx[i - 1]; } inline int get_next(int x) { int i = find_block(x + 1); return pool[bid[i]][find_pos(i,x + 1)]; } int main() { n = read(),m = read(); for (int i = 1; i <= n; i++) { a[i] = read(); } a[++n] = inf; // 哨兵 a[++n] = -inf; sort(a + 1,a + n + 1); for (int s = 1; s <= n; s += BS) { int len = min(BS,n - s + 1),id = ++ns; memcpy(pool[id] + 1,a + s,len * sizeof(int)); ++nb; bid[nb] = id; sz[nb] = len; mx[nb] = a[s + len - 1]; } tot = n; build_fw(); int last = 0,ans = 0; for (int i = 1; i <= m; i++) { int op = read(),x = read() ^ last; if (op == 1) { insert(x); } else if (op == 2) { erase(x); } else if (op == 3) { last = get_rank(x); ans ^= last; } else if (op == 4) { last = get_kth(x); ans ^= last; } else if (op == 5) { last = get_prev(x); ans ^= last; } else { last = get_next(x); ans ^= last; } } cout << ans << "\n"; return 0; }::: :::info[代码(封装)]
class BLT { public: static const int BS = 200; // 初始块大小 static const int CAP = 2 * BS; // 块容量 static const int B = 2 * N / BS + 256; // 总块数 static const int inf = 0x7fffffff; int pool[B][CAP + 1]; // 块的数据 int bid[B]; // 第i块所属槽位 int sz[B]; // 块的大小 int mx[B]; // 块内最大值 int fw[B]; // 维护块大小的树状数组 int ns; // 开的块的个数 int nb; // 当前块的个数 int tot; // 当前元素个数 inline void build() { for (int i = 1; i <= n; i++) { a[i] = read(); } a[++n] = inf; // 哨兵 a[++n] = -inf; sort(a + 1,a + n + 1); for (int s = 1; s <= n; s += BS) { int len = min(BS,(int)(n - s + 1)),id = ++ns; memcpy(pool[id] + 1,a + s,len * sizeof(int)); ++nb; bid[nb] = id; sz[nb] = len; mx[nb] = a[s + len - 1]; } tot = n; build_fw(); } inline void build_fw() { // 线性建树状数组 memcpy(fw + 1,sz + 1,nb * sizeof(int)); for (int i = 1; i <= nb; i++) { int j = i + (i & -i); if (j <= nb) fw[j] += fw[i]; } } inline void add_fw(int x,int v) { for (; x <= nb; x += x & -x) fw[x] += v; } inline int sum_fw(int x) { int ans = 0; for (; x; x -= x & -x) ans += fw[x]; return ans; } inline int find_block(int x) { // 找第一个mx>=x的块 int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { if (i + pw <= nb && mx[i + pw] < x) { i += pw; } } return i + 1; } inline int find_pos(int i,int x) { // 找到块内第一个>=x的位置 int *b = pool[bid[i]],j = 1; while (j + 9 <= sz[i] && b[j + 9] < x) j += 10; while (j <= sz[i] && b[j] < x) j++; return j; } inline void split(int i) { // 分裂第i个块 int h = sz[i] >> 1,m = sz[i] - h; int id = ++ns; memcpy(pool[id] + 1,pool[bid[i]] + h + 1,m * sizeof(int)); for (int j = nb; j > i; j--) { bid[j + 1] = bid[j]; sz[j + 1] = sz[j]; mx[j + 1] = mx[j]; } bid[i + 1] = id; sz[i + 1] = m,mx[i + 1] = pool[id][m]; sz[i] = h,mx[i] = pool[bid[i]][h]; nb++; build_fw(); } inline void remove(int i) { // 删除第i个块 for (int j = i; j < nb;j++) { bid[j] = bid[j + 1]; sz[j] = sz[j + 1]; mx[j] = mx[j + 1]; } nb--; build_fw(); } inline void insert(int x) { tot++; int i = find_block(x),p; if (i == nb + 1) i = nb,p = sz[nb] + 1; else p = find_pos(i,x); if (sz[i] == CAP) { split(i); if (p > sz[i]) p -= sz[i],i++; // 分到了右边的块 } int *b = pool[bid[i]]; memmove(b + p + 1,b + p,(sz[i] - p + 1) * sizeof(int)); b[p] = x,sz[i]++,mx[i] = b[sz[i]]; add_fw(i,1); } inline void erase(int x) { tot--; int i = find_block(x),p = find_pos(i,x); if (sz[i] == 1) { remove(i); return; } int *b = pool[bid[i]]; memmove(b + p,b + p + 1,(sz[i] - p) * sizeof(int)); sz[i]--,mx[i] = b[sz[i]]; add_fw(i,-1); } inline int get_rank(int x) { int i = find_block(x); if (i == nb + 1) return tot; return sum_fw(i - 1) + find_pos(i,x) - 1; } inline int get_kth(int k) { k++; int i = 0; for (int pw = 1 << (31 ^ clz(nb)); pw; pw >>= 1) { // 树状数组倍增 if (i + pw <= nb && fw[i + pw] < k) { i += pw; k -= fw[i]; } } return pool[bid[i + 1]][k]; } inline int get_prev(int x) { int i = find_block(x); if (i == nb + 1) return mx[nb]; else if (pool[bid[i]][1] < x) return pool[bid[i]][find_pos(i,x) - 1]; else return mx[i - 1]; } inline int get_next(int x) { int i = find_block(x + 1); return pool[bid[i]][find_pos(i,x + 1)]; } inline void clear() { ns = 1,nb = 1,tot = 2; pool[1][1] = -inf,pool[1][2] = inf; bid[1] = 1,sz[1] = 2,mx[1] = inf; fw[1] = 2; } };
- 若该块最小值
:::
四:复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 预处理 | 基数排序 / sort |
|
find_block |
||
find_pos |
||
split |
单次 |
单次建树状数组 memcpy insert |
remove |
单次 |
|
build_fw |
||
add_fw / sum_fw |
||
insert / erase |
均摊 |
memmove split |
get_rank / get_prev / get_next |
||
get_kth |
||
clear |
当
空间复杂度:pool 的空间约为 a 的空间约为
五:实测(用的是上面那一份代码)
洛谷上 P6136 跑了 2.29s,最优解第一页。
本机用 WorkBuddy 测的,
六:优劣分析
优点
- 常数小。
- 时空复杂度低(相较于普通块状链表)。
缺点
- 码量相对于平衡树较大。
- 无法区间操作。
七:为什么这么快
- 缓存局部性好,
mx,fw和当前操作的块常驻 L1,而平衡树节点散布主存。 memmove和memcpy批量搬运。- 树状数组本身常数低。
- 全静态数组。
八:如何继续优化
将树状数组再分一次块,修改时只将树状数组后半更新,批量重建,SIMD 等,但以上操作均会增大码量,故在此略去不表。