高级数据结构笔记
樹套樹
顧名思義，就是一個樹套一個樹。。。
廣義的樹套樹是指嵌套多層的數據結構。常見的有：線段樹套線段樹（二維線段樹），線段樹套平衡樹（“二逼平衡樹”），分塊套平衡樹，樹狀數組套線段樹（帶修主席樹）等等。
在這里，由于 set，map 等 STL 內部實現是平衡樹，因此將這些 STL 的嵌套也算作樹套樹。
樹套樹解決偏序問題
樹套樹最典型的應用就是解決各種各樣的偏序問題。
P3810 【模板】三維偏序（陌上花開）
經典解法是 CDQ 分治。這里使用樹狀數組套權值線段樹解決。
首先第一維是經典的排序，第二維可以使用樹狀數組維護起來。樹狀數組的每個節點維護一棵動態開點線段樹，維護這個節點范圍內所有節點的第三維信息。
時間復雜度 \(O(n \log ^ 2 n)\)，空間 \(O(n \log n)\)。
放一下主體部分代碼：
struct node {
int ls, rs, s;
}tr[M];
#define lc tr[u].ls
#define rc tr[u].rs
#define mid (l + r >> 1)
void add(int &u, int l, int r, int x) {
if (!u) u = ++ cnt; tr[u].s ++ ;
if (l == r) return;
if (x <= mid) add(lc, l, mid, x);
else add(rc, mid + 1, r, x);
}
void ADD(int x, int y) {
for (int i = x; i <= m; i += (i & -i)) add(rt[i], 1, m, y);
}
int sum(int &u, int l, int r, int x) {
if (!u or l > x) return 0;
if (r <= x) return tr[u].s;
return sum(lc, l, mid, x) + sum(rc, mid + 1, r, x);
}
int SUM(int x, int y, int s = 0) {
for (int i = x; i; i -= (i & -i)) s += sum(rt[i], 1, m, y); return s;
}
P3157 [CQOI2011] 動態逆序對
將刪點操作倒過來，就是逆序加點的過程。
將加點的順序（即時間軸）看做第一維，將下標看做第二維，將權值看做第三維。
這就是典型的三維偏序問題。直接樹套樹帶走。
提交記錄
- Levko and Array
樹套樹解決二維數點問題
這里的二維數點定義比較廣泛，包括點個數的計數，以及滿足某些性質的點集查詢等。
通常，二維數點問題有以下幾種做法：
-
將第一維分塊，塊內套
set等數據結構維護第二維。同時對于每個 \(x\) 坐標建立一個set，用于維護散塊信息。 -
對第一維建線段樹，線段樹節點里面套
set/ 平衡樹。 -
對第一維建樹狀數組，樹狀數組每個節點里套
set/ 平衡樹。
對于第一種方法，直接對于整塊 / 散塊里的平衡樹 lower_bound 即可。
對于第二種方法，定位到線段樹上的 \(O(\log n)\) 個區間之后和第一種一樣。
對于第三種方法，需要根據情況具體分析。有時需要維護樹狀數組后綴 \(\max\) 或者前綴 \(\max\)，有時需要維護點數等等。優勢是常數小。
CF19D Points
很好的一道題。但是由于題目喪心病狂的卡常，我至今沒有用樹狀數組套 set 卡過去。
題目顯然是二維數點，屬于求滿足某種條件的點集類型題目。條件是某個點右上方的最左下的點。
第一種思路是分塊套 set。對于橫縱坐標離散化之后，對于每個橫坐標維護一個 set，記錄橫坐標為該值的所有縱坐標。同時對每個塊維護一個類型為 pair 的 set，維護橫坐標在該塊內的所有點。
每次插入和查詢復雜度都是 \(O(\log n)\)。查詢復雜度需要查詢 \(O(\sqrt n)\) 個整塊，每個整塊需要 \(O(\log n)\) 的復雜度。需要查詢 \(O(\sqrt n)\) 個單點，單點復雜度 \(O(\log n)\)。因此總復雜度 \(O(m \sqrt n \log n)\)。輕松的跑過去了。
第二種思路是樹狀數組套 set。對于縱坐標用樹狀數組維護，內層套 set 維護橫坐標。插入的時候只需要在右端點 \(< y\) 的節點的 set 內插點就可以了。對于查詢操作，只需要在左端點 \(\ge y\) 的節點 set 內 lower_bound 即可。復雜度 \(O(m \log ^ 2 n)\)。
不知道為什么，常數和復雜度都小的樹狀數組套 set 沒有卡過去/kk
分塊套 set 代碼
樹狀數組套 set ：
set<PII> s[N]; vector<int> p;
int n, lim;
struct Q { int op, x, y; }q[N];
void add(int x, int y) {
for (int i = y; i; i -= (i & -i)) s[i].insert(mp(x, y));
}
void del(int x, int y) {
for (int i = y; i; i -= (i & -i)) s[i].erase(mp(x, y));
}
PII ask(int x, int y) {
PII ans = mp(INF, INF);
for (int i = y; i <= lim; i += (i & -i))
ans = min(ans, *s[i].lower_bound(mp(x, y)));
return ans;
}
int main() {
read(n);
rep(i, 1, n) {
char ch[7]; int x, y;
scanf("%s", ch); read(x, y);
if (*ch == 'a') q[i] = {0, x, y};
if (*ch == 'r') q[i] = {1, x, y};
if (*ch == 'f') q[i] = {2, ++ x, ++ y};
p.push_back(y);
} sort(all(p)); p.resize(unique(all(p)) - p.begin());
lim = p.size();
auto find = [](int x) -> int {
return lower_bound(all(p), x) - p.begin() + 1;
};
rep(i, 1, n) q[i].y = find(q[i].y);
rep(i, 1, lim) s[i].insert(mp(INF, INF));
rep(i, 1, n) {
if (q[i].op == 0) add(q[i].x, q[i].y);
if (q[i].op == 1) del(q[i].x, q[i].y);
if (q[i].op == 2) {
register PII ans = ask(q[i].x, q[i].y);
if (ans.first == INF) puts("-1");
else write(' ', ans.first, p[ans.second - 1]), pc('\n');
}
} return 0;
}
Intersection of Permutations
比較套路的一道題。若有 \(b_x = a_y\)，那么記 \(t_x = y\)。
問題轉化成了：
-
查詢操作：查詢在 \(l_b \sim r_b\) 中，有多少 \(t_i \in [l_a, r_a] \bigcup \mathbb{Z}\)。
-
修改操作：交換 \(t_x, t_y\)。
這是一個帶修的二維數點，直接樹狀數組套權值線段樹帶走。
注意要寫空間回收，要不然會 MLE。
struct node { int ls, rs, s; }tr[M];
#define ls tr[u].ls
#define rs tr[u].rs
#define mid (l + r >> 1)
int New() { return !top ? ++ cnt : stk[top -- ]; }
void add(int &u, int l, int r, int x, int v) {
if (l > x or r < x) return;
if (!u) u = New(); tr[u].s += v; if (l == r) return;
add(ls, l, mid, x, v), add(rs, mid + 1, r, x, v);
if (!tr[u].s) stk[ ++ top] = u, u = 0;
}
void ADD(int x, int p, int v) {
for (int i = x; i <= n; i += (i & -i)) add(rt[i], 1, n, p, v);
}
int ask(int u, int l, int r, int L, int R) {
if (!u or r < L or l > R) return 0;
if (l >= L and r <= R) return tr[u].s;
return ask(ls, l, mid, L, R) + ask(rs, mid + 1, r, L, R);
}
int ASK(int la, int ra, int lb, int rb, int s = 0) { lb -- ;
for (int i = rb; i; i -= (i & -i)) s += ask(rt[i], 1, n, la, ra);
for (int i = lb; i; i -= (i & -i)) s -= ask(rt[i], 1, n, la, ra); return s;
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]), bin[a[i]] = i;
rep(i, 1, n) scanf("%d", &b[i]);
rep(i, 1, n) t[i] = bin[b[i]], ADD(i, t[i], 1);
while (m -- ) {
int op, la, ra, lb, rb, x, y;
scanf("%d", &op);
if (op & 1) {
scanf("%d%d%d%d", &la, &ra, &lb, &rb);
printf("%d\n", ASK(la, ra, lb, rb));
} else {
scanf("%d%d", &x, &y);
ADD(x, t[x], -1); ADD(y, t[y], -1);
swap(t[x], t[y]); ADD(x, t[x], 1); ADD(y, t[y], 1);
}
} return 0;
}
樹套樹解決帶修區間第 \(k\) 大問題
不帶修的區間第 \(k\) 大，正經解法就是主席樹。
那么如果帶修了呢？
可以外層一個樹狀數組維護下標，內層一個權值線段樹維護這個區間的權值。
這樣相當于把一棵主席樹拆成了許多個動態開點線段樹。
修改時，每次修改樹狀數組的 \(\log\) 個節點，每修改一個節點需要一個老哥，所以就是 \(O(\log ^ 2 n)\)。
查詢就是前綴和的容斥。前綴和要在樹狀數組上做，所以是兩個 \(\log\)。
經典例題：
P2617 Dynamic Rankings
放一下主體部分代碼：
struct node {
int ls, rs, s;
}tr[M]; int rt[N];
vector<int> L, R;
int n, m, cnt, a[N];
#define lc tr[u].ls
#define rc tr[u].rs
#define mid (l + r >> 1)
void add(int &u, int l, int r, int x, int v) {
if (l > x or r < x) return;
if (!u) u = ++ cnt; tr[u].s += v;
if (l == r) return;
add(lc, l, mid, x, v); add(rc, mid + 1, r, x, v);
}
void ADD(int x, int v, int c) {
for (int i = x; i <= n; i += (i & -i))
add(rt[i], 0, V, v, c);
}
int ask(int l, int r, int k) {
if (l == r) return r; int s = 0;
for (auto &u : R) s += tr[lc].s;
for (auto &u : L) s -= tr[lc].s;
if (k <= s) {
for (auto &u : L) u = lc;
for (auto &u : R) u = lc;
return ask(l, mid, k);
}
for (auto &u : L) u = rc;
for (auto &u : R) u = rc;
return ask(mid + 1, r, k - s);
}
int ASK(int l, int r, int k) {
L.clear(); R.clear(); l -- ;
for (int i = r; i; i -= (i & -i)) R.pb(rt[i]);
for (int i = l; i; i -= (i & -i)) L.pb(rt[i]);
return ask(0, V, k);
}
Summary： 在大部分時候，需要維護的信息具有左 / 右端點固定或者可差分性時，使用樹狀數組套數據結構是一個不錯的選擇。
當然，有時分塊套數據結構可以獲得意想不到的小常數。
總結
- 上一篇： 使用Spring AI让你的Spring
- 下一篇： 从像素到洞见：图像分类技术的全方位解读