線段樹的各種擴展
線段樹的各種擴展
前情提要線段樹, 算法競賽掌管區間的神, 權值數據結構水各種題.
小技巧
動態開點
這篇博客所有的線段樹擴展都基于動態開點, 所以先講一下.
先申請一個很長的數組, 需要新結點就從數組里申請.
這是一種內存池思想, 可以避免內存的多次申請與釋放 (更多的是可以避免指針), 在有文字記載的首任指針神教教主一扶蘇一的代碼中, 甚至會直接把這個很長的數組稱為 \(pool\).
int rt = 0, cntt = 0;
int ls[NN << 5], rs[NN << 5];
T val[NN << 5]; // 這個按照需要來寫類型, 下面所有T都是同樣
inline // 這個函數是申請結點用的, 一般直接寫++cntt, 不寫函數
int newnode() {
return ++cntt;
}
為什么是 \(32\) 倍空間呢?
每次新建都需要從根到葉子建一串結點, 就是 \(\log V\) 個, 所以開\(32\) (int的最大長度) 倍空間即可 (當然 long long 是 \(64\)).
很顯然修改可能要新建, 但是詢問和線段樹上二分是不需要新建的.
放一下代碼, 單點修改區間查詢和線段樹上二分 (這篇博客介紹的東西都是只需要單點修改的, 涉及區間修改也只需要打上標記即可).
傳入指針是因為C語言沒有引用這種東西, 有條件建議是傳引用.
傳指針是因為不想傳引用, 不代表是指針線段樹. --指針神教教主Defad
void update(int *x, int l, int r, int I, T k) {
if (!*x) *x = ++cntt;
if (l == r) {
val[*x] += k;
return;
} else {
int m = l + r >> 1;
if (I <= m)
update(ls + *x, l, m, I, k);
else
update(rs + *x, m + 1, r, I, k);
return pushup(*x);
}
}
T query(int x, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return val[x];
} else {
int m = l + r >> 1; T s = 0; // 置空
if (L <= m)
s += query(ls[x], l, m, L, R);
if (m + 1 <= R)
// 3F曾經某次At-ABC因為這里寫成 s == query 導致罰時, 希望同學們引以為戒
s += query(rs[x], m + 1, r, L, R);
return s;
}
int kth(int x, int l, int r, T k) {
if (l == r) {
return l;
} else {
int m = l + r >> 1;
if (k <= val[ls[x]])
return kth(ls[x], l, m, k);
else if (k <= val[x])
return kth(rs[x], m + 1, r, k - val[ls[x]]);
else // 這個根據題目來, 有時是 -1, 有時是 r 或 r + 1
return -1;
}
}
不知有沒有同學想過為什么這里訪問了 \(ls\), 但是有可能 \(ls\) 沒有用過就是 \(0\), 反正Defad是想過的.
因為 \(0\) 是始終都不會被修改的, 所以一直有 \(ls_{0} = 0, rs_{0} = 0, val_{0} = 0\), 所以不會出問題.
但是如果用指針線段樹就要注意了, 沒有初始化的是 NULL, 訪問空指針就是RE, 直接掛大分.
標記永久化
線段樹上的一種技巧, 不需要進行 pushdown 就能快很多, 最重要的是在標記難以下傳時可以直接維護標記.
首先區間修改的時候打標記, 這里用普通線段樹舉例.
inline
void pushup(int x, int l, int r) {
val[x] = val[x << 1] + val[x << 1 | 1] + tag[x] * (r - l + 1);
}
void update(int x, int l, int r, int L, int R, ll k) {
if (L <= l && r <= R) {
val[x] += k * (r - l + 1);
tag[x] += k;
return;
} else {
int m = l + r >> 1;
if (L <= m)
update(x << 1, l, m, L, R, k);
if (m + 1 <= R)
update(x << 1 | 1, m + 1, r, L, R, k);
return pushup(x, l, r);
}
}
然后查詢時帶著標記查詢.
ll query(int x, int l, int r, int L, int R, ll k) {
if (L <= l && r <= R) {
return val[x] + k * (r - l + 1);
} else {
int m = l + r >> 1; ll s = 0LL;
if (L <= m)
s += query(x << 1, l, m, L, R, k + tag[x]);
if (m + 1 <= R)
s += query(x << 1 | 1, m + 1, r, L, R, k + tag[x]);
return s;
}
}
動態開點權值線段樹
好消息是不需要離散化, 壞消息是容易寫掛.
以上次的平衡樹舉例.
直接把區間長度開到 \([-1 * 10^{7}, 1 * 10^{7}]\), 然后把上次的代碼的離散化刪掉, 提交.
線段樹分裂合并
一般用于集合的分裂合并, 所以多數是權值線段樹.
線段樹合并
合并兩個可重集, 這兩個可重集分別是用權值線段樹維護的.
首先, 肯定要遞歸整個線段樹.
其次, 如果當前可重集 \(x\) 或 \(y\) 的這個結點為空, 就返回非空的.
void merge(int x, int y, int l, int r) {
if (!x || !y) return x ^ y; // 返回非空的
if (l == r) {
val[x] += val[y];
return x;
} else {
int m = l + r >> 1;
ls[x] = merge(ls[x], ls[y], l, m);
rs[x] = merge(rs[x], rs[y], m + 1, r);
pushup(x);
return x;
}
}
線段樹分裂
把可重集 \(y\) 的所有在 \([L, R]\) 區間內的數放到新的可重集 \(x\), 并在 \(y\) 中刪掉這些數.
首先肯定要申請 \(x\) 的結點.
然后重要的, 在區間內就 \(ls, rs, val\) 都要傳遞, 清空可以偷懶直接給這個結點的父結點的這個兒子變成 \(0\).
int split(int *y, int l, int r, int L, int R) {
int x = ++cntt;
if (L <= l && r <= R) {
ls[x] = ls[*y];
rs[x] = rs[*y];
val[x] = val[*y];
*y = 0;
return x;
} else {
int m = l + r >> 1;
if (L <= m)
ls[x] = split(ls + *y, l, m, L, R);
if (m + 1 <= R)
rs[x] = split(rs + *y, m + 1, r, L, R);
pushup(*y);
pushup(x);
return x;
}
}
板子
需要記錄多個根, 使用一個 \(cntr\) 記錄當前有多少個根, 分裂出來直接 \(cntr := cntr + 1\) 然后給到 \(rt_{cntr}\) 即可.
持久化線段樹
本期唯一不涉及權值的線段樹, 只需要在歷史版本上單點修改單點查詢.
首先這次如果有初始化就必須建樹了, 不然就不是版本 \(0\) 了.
inline
void pushup(int x) {
val[x] = val[ls[x]] + val[rs[x]];
}
void build(int *x, int l, int r) {
if (!*x) *x = ++cntt;
if (l == r) {
val[*x] = a[l];
return;
} else {
int m = l + r >> 1;
build(ls + *x, l, m);
build(rs + *x, m + 1, r);
return pushup(*x);
}
}
然后考慮修改.
A. 把原來的線段樹復制一遍.
B. 只把要修改的一串修改, 其他的用原來的.
顯然, 前者極易MLE, 而后者較省空間.
void update(int *x, int y, int l, int r, int I, ll k) {
if (!*x) *x = ++cntt;
if (l == r) {
val[*x] = k;
return;
} else {
int m = l + r >> 1;
if (I <= m) {
rs[*x] = rs[y];
update(ls + *x, ls[y], l, m, I, k);
} else {
ls[*x] = ls[y];
update(rs + *x, rs[y], m + 1, r, I, k);
}
return pushup(*x);
}
}
查詢如果要新建相同版本, 可以傳遞一下 \(rt_{h}\) 到 \(rt_{i}\), 把歷史版本的根直接給到當前版本.
普通的動態開點線段樹單點查詢.
ll query(int x, int l, int r, int I) {
if (l == r) {
return val[x];
} else {
int m = l + r >> 1;
if (I <= m)
return query(ls[x], l, m, I);
else
return query(rs[x], m + 1, r, I);
}
}
主席樹
動態開點權值線段樹, 并不是持久化的, 因為持久化需要支持修改操作, 而主席樹的修改操作并不是對于值進行修改, 而是維護數組的.
第一步, 離散化.
第二步, 建樹.
這個建樹和普通線段樹的建樹不一樣, 要建立 \(N\) 個權值線段樹 (顯然要動態開點并且每次只新建一串), 第 \(i\) 個權值線段樹維護數組 \(a\) 的 \(1\) 到 \(i\) 中出現的所有的數.
指針神教上一任教主Wild-Donkey形容主席樹為"批判的繼承".
inline
void pushup(int x) {
val[x] = val[ls[x]] + val[rs[x]];
}
void update(int *x, int y, int l, int r, int I, int k) {
if (!*x) *x = ++cntt;
if (l == r) {
val[*x] = val[y] + k;
return;
} else {
int m = l + r >> 1;
if (I <= m) {
rs[*x] = rs[y];
update(ls + *x, ls[y], l, m, I, k);
} else {
ls[*x] = ls[y];
update(rs + *x, rs[y], m + 1, r, I, k);
}
return pushup(*x);
}
}
f1 (i, 1, S, 1) { // 這是main里的離散化后的建樹部分
update(rt + i, rt[i - 1], 1, N, a[i], 1);
}
查詢.
線段樹上二分, 注意要二分的是 \(x - 1\) 和 \(y\) , 至于為什么可以想一想前綴和.
int kth(int x, int y, int l, int r, int k) {
if (l == r) {
return l;
} else {
int m = l + r >> 1;
if (k <= val[ls[y]] - val[ls[x]])
return kth(ls[x], ls[y], l, m, k);
else if (k <= val[y] - val[x])
return kth(rs[x], rs[y], m + 1, r, k - (val[ls[y]] - val[ls[x]]));
else
return -1;
}
}
最后輸出的是?
A. a[query(rt[x - 1], rt[y], 1, N, k)]
B. b[query(rt[x - 1], rt[y], 1, N, k)]
顯然要選B, 但是Defad在SPOJ上交主席樹時在這里也出過逝, 所以也要引以為戒, a 是離散化后的, b 是原數組去重的.
浙公網安備 33010602011771號