Kinetic Segment Tree
Cây phân đoạn động học: duy trì max của các hàm bậc nhất a_i*t + b_i trên đoạn khi thời gian t chỉ tăng, hỗ trợ cập nhật điểm, với heaten khấu hao O(log^2 N).
Kinetic Segment Tree (KST, cây phân đoạn "động học") giải bài toán sau: có vị trí, vị trí giữ một hàm bậc nhất (hiểu là phần tử có giá trị ban đầu và lớn lên với tốc độ riêng ). Ta cần hỗ trợ ba thao tác:
update(i, a, b): thay hàm ở vị trí bằng ;heaten(t): cho thời gian trôi tới , với điều kiện không bao giờ giảm;query(l, r): trả về tại thời điểm hiện tại.
Cách ngây thơ tốn mỗi truy vấn. Cây phân đoạn thường không dùng được vì phần tử lớn nhất của một đoạn thay đổi theo thời gian. KST giữ ở mỗi nút "đường thẳng đang thắng" kèm thời điểm tan chảy (melt), tức lúc sớm nhất mà kết quả trong cây con có thể đổi; heaten chỉ sửa những nút đã "tan". Truy vấn và cập nhật tốn , còn heaten tốn khấu hao (amortized).
Ý tưởng / Trực giác
Mỗi nút là một "giải đấu" giữa hai đường thẳng
Giống cây phân đoạn max thông thường, nút phụ trách đoạn và lưu đường thẳng thắng , tức hàm có giá trị lớn nhất trong đoạn tại thời điểm hiện tại . Nút cha so sánh hai người thắng của hai con: người nào lớn hơn tại thì thắng. Cấu trúc này còn gọi là kinetic tournament (giải đấu động học), do Basch, Guibas và Hershberger đề xuất trong lĩnh vực hình học tính toán ("Data Structures for Mobile Data", 1997).
Vấn đề: khi tăng, người thắng có thể bị vượt. Nhưng ta biết trước khi nào. Nếu ở nút , người thắng là và người thua là :
- Nếu thì không bao giờ vượt được nữa (đang thua, lại tăng chậm hơn hoặc bằng).
- Nếu thì đuổi kịp tại thời điểm đầu tiên có , tức
Thời điểm tan chảy
Gọi là thời điểm sớm nhất mà bất kỳ trận đấu nào trong cây con của đổi kết quả: với khi người thua ở không thể vượt. Lá có .
Bất biến: mọi nút đều có . Khi đó người thắng ở mọi nút vẫn đúng tại thời điểm , nên query chỉ cần lấy max giá trị tại của các nút phủ , y hệt cây phân đoạn thường.
heaten: chỉ đi vào chỗ đã tan
Khi heaten(t) đặt , những nút có có thể đã sai. Ta đi từ gốc: nếu thì cả cây con vẫn đúng, dừng ngay; ngược lại đi xuống hai con, sửa chúng xong rồi tính lại (chọn lại người thắng tại , tính lại melt). Nhờ melt là min trên cả cây con, ta không bao giờ đi vào một cây con không có gì thay đổi, nên chi phí chỉ tỉ lệ với số trận đấu thực sự đổi kết quả nhân với độ sâu.
Vì sao số lần đổi người thắng không lớn
Xét một nút cố định trong một khoảng thời gian không có update. Khi người thắng đổi từ sang thì : hệ số góc của người thắng chỉ tăng. Đây chính là tính chất của đường bao trên (upper envelope) các đường thẳng: đi từ trái sang phải, hệ số góc của đoạn tối ưu tăng dần. Vì vậy nút phụ trách vị trí đổi người thắng tối đa lần, tổng trên mọi nút là lần, mỗi lần được phát hiện bằng một đường đi dài từ gốc. Không có cập nhật, toàn bộ quá trình heaten tốn .
Khi có update điểm, lập luận khấu hao phức tạp hơn vì một cập nhật "làm mới" nút trên đường từ lá lên gốc. Các bài viết về KST trên Codeforces (blog của ekzhang về Kinetic Tournament dùng ở Facebook Hacker Cup 2020, và bài của koosaga được bobr_babizon dịch ra tiếng Anh) nêu cận khấu hao cho mỗi heaten. Cận đã chứng minh chặt chẽ khi xen kẽ cập nhật điểm là (dựa trên dãy Davenport-Schinzel), còn được tin là đúng và chạy nhanh như vậy trong thực tế.
Ví dụ chạy tay
hàm, thời điểm bắt đầu :
| Vị trí | Hàm | ||||
|---|---|---|---|---|---|
| 1 | 6 | 6 | 6 | 6 | |
| 2 | 3 | 5 | 7 | 9 | |
| 3 | 0 | 4 | 8 | 12 | |
| 4 | 8 | 6 | 4 | 2 |
Cây phân đoạn có 7 nút: gốc 1 phụ trách , nút 2 phụ trách , nút 3 phụ trách , các lá 4, 5, 6, 7 ứng với vị trí 1, 2, 3, 4. Nhãn bên cạnh mỗi nút ghi người thắng và melt (inf là ). Bấm qua từng bước để xem các nút được tính lại.
tree 1 2 1 3 2 4 2 5 3 6 3 7 step T = 0: dựng cây. Ở gốc f4 = 8 thắng f1 = 6, nhưng f1 dốc hơn (0 > -1) nên đuổi kịp tại ceil((8-6)/(0+1)) = 2 label 1 f4, melt=2 label 2 f1, melt=3 label 3 f4, melt=3 label 4 f1 label 5 f2 label 6 f3 label 7 f4 step heaten(2): chỉ gốc có melt = 2 <= 2. Nút 2, 3 có melt 3 > 2 nên bỏ qua. Gốc tính lại: f1 = 6 hòa f4 = 6, chọn f1 (hệ số góc lớn hơn) clear highlight orange 1 label 1 f1, melt=3 label 2 f1, melt=3 label 3 f4, melt=3 label 4 f1 label 5 f2 label 6 f3 label 7 f4 step heaten(4): gốc melt 3 <= 4, đi xuống. Nút 2: f2 = 7 thắng f1 = 6. Nút 3: f3 = 8 thắng f4 = 4. Gốc: f3 = 8 thắng f2 = 7, hết cặp nào đuổi kịp clear highlight orange 2 3 1 label 1 f3, melt=inf label 2 f2, melt=inf label 3 f3, melt=inf label 4 f1 label 5 f2 label 6 f3 label 7 f4 step heaten(6): gốc có melt = inf > 6, dừng ngay, không nút nào bị thăm clear highlight gray 1 label 1 f3, melt=inf label 2 f2, melt=inf label 3 f3, melt=inf label 4 f1 label 5 f2 label 6 f3 label 7 f4 step update(4, 3, -5) tại T = 6: f4 mới = 3t - 5 = 13. Tính lại đường 7, 3, 1: f4 thắng ở nút 3 và gốc clear highlight green 7 3 1 7-3 3-1 label 1 f4, melt=inf label 2 f2, melt=inf label 3 f4, melt=inf label 4 f1 label 5 f2 label 6 f3 label 7 f4 = 3t-5
Chi tiết các melt lúc dựng cây ():
| Nút | Thắng | Thua | Thua đuổi kịp? | melt | |
|---|---|---|---|---|---|
| 2 | (6) | (3) | , có | 3 | |
| 3 | (8) | (0) | , có | 3 | |
| 1 | (8) | (6) | , có |
Dãy thao tác và kết quả (khớp với output chương trình bên dưới):
| Thao tác | Kết quả | Kiểm tra trực tiếp | |
|---|---|---|---|
query(1, 4) |
0 | 8 | |
heaten(2), query(1, 4) |
2 | 6 | |
heaten(4), query(1, 2) |
4 | 7 | |
heaten(6), update(4, 3, -5), query(1, 4) |
6 | 13 | |
query(1, 3) |
6 | 12 |
Để ý heaten(6) không thăm nút nào: sau mọi người thắng đã là đường dốc nhất trong cây con của mình, không ai đuổi kịp được nữa.
Cài đặt
Chương trình đọc , , rồi cặp , rồi thao tác: 1 i a b (cập nhật), 2 t (heaten, không giảm), 3 l r (in max). Thời điểm ban đầu là . Hai bản cho cùng output; đã được đối chiếu với brute force mỗi truy vấn trên 3000 bộ test ngẫu nhiên (có hệ số góc âm, hòa nhau, thời gian đứng yên).
Input mẫu (đúng ví dụ chạy tay):
4 9
0 6
1 3
2 0
-1 8
3 1 4
2 2
3 1 4
2 4
3 1 2
2 6
1 4 3 -5
3 1 4
3 1 3
Output:
8
6
7
13
12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX; // "never melts"
const ll NEG = LLONG_MIN / 4; // value of an empty position
struct Line {
ll a, b;
bool empty;
ll eval(ll t) const { return empty ? NEG : a * t + b; }
};
// ceil(p / q) for q > 0, works with negative p
ll ceilDiv(ll p, ll q) { return p / q + ((p % q != 0) && ((p > 0) == (q > 0))); }
struct KineticSegTree {
int n;
ll T; // current time, only increases
vector<Line> win; // winner line of each node at time T
vector<ll> melt; // smallest time > T at which some winner in the subtree changes
KineticSegTree(int n, ll t0) : n(n), T(t0), win(4 * n, {0, 0, true}), melt(4 * n, INF) {}
// Recompute node v from its children (children are already valid at time T).
void pull(int v) {
const Line &L = win[2 * v], &R = win[2 * v + 1];
ll vl = L.eval(T), vr = R.eval(T);
// Tie: prefer the larger slope, it stays ahead for every later t.
bool leftWins = vl > vr || (vl == vr && L.a >= R.a);
const Line &w = leftWins ? L : R, &o = leftWins ? R : L;
win[v] = w;
melt[v] = min(melt[2 * v], melt[2 * v + 1]);
if (!w.empty && !o.empty && o.a > w.a) {
// o catches up with w at the first t with o(t) >= w(t)
ll t = ceilDiv(w.b - o.b, o.a - w.a);
melt[v] = min(melt[v], t); // t > T because w(T) > o(T) or tie broken by slope
}
}
void update(int v, int l, int r, int pos, const Line &ln) {
if (l == r) { win[v] = ln; melt[v] = INF; return; }
int m = (l + r) / 2;
if (pos <= m) update(2 * v, l, m, pos, ln);
else update(2 * v + 1, m + 1, r, pos, ln);
pull(v);
}
// Only visit subtrees in which some winner changes by time T.
void heat(int v, int l, int r) {
if (melt[v] > T) return;
int m = (l + r) / 2;
heat(2 * v, l, m);
heat(2 * v + 1, m + 1, r);
pull(v);
}
ll query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return NEG;
if (ql <= l && r <= qr) return win[v].eval(T);
int m = (l + r) / 2;
return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
// Public interface (positions 1..n)
void update(int i, ll a, ll b) { update(1, 1, n, i, {a, b, false}); }
void erase(int i) { update(1, 1, n, i, {0, 0, true}); }
void heaten(ll t) { assert(t >= T); T = t; heat(1, 1, n); }
ll query(int l, int r) { return query(1, 1, n, l, r); }
};
int main() {
// Input: n q, then n lines "a b", then q operations:
// 1 i a b : replace line i by a*t + b
// 2 t : set current time to t (t never decreases)
// 3 l r : print max over i in [l, r] of a_i * t + b_i
int n, q;
scanf("%d %d", &n, &q);
KineticSegTree st(n, 0);
for (int i = 1; i <= n; i++) {
ll a, b;
scanf("%lld %lld", &a, &b);
st.update(i, a, b);
}
while (q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int i; ll a, b;
scanf("%d %lld %lld", &i, &a, &b);
st.update(i, a, b);
} else if (type == 2) {
ll t;
scanf("%lld", &t);
st.heaten(t);
} else {
int l, r;
scanf("%d %d", &l, &r);
printf("%lld\n", st.query(l, r));
}
}
}
import sys
INF = float('inf') # "never melts"
NEG = -(1 << 62) # value of an empty position
class KineticSegTree:
def __init__(self, n, t0=0):
self.n = n
self.T = t0 # current time, only increases
self.A = [0] * (4 * n) # winner line of each node: A*t + B
self.B = [0] * (4 * n)
self.E = [True] * (4 * n) # True if the node has no line
self.melt = [INF] * (4 * n)
def _val(self, v):
return NEG if self.E[v] else self.A[v] * self.T + self.B[v]
def _pull(self, v):
L, R = 2 * v, 2 * v + 1
vl, vr = self._val(L), self._val(R)
# Tie: prefer the larger slope, it stays ahead for every later t.
if vl > vr or (vl == vr and self.A[L] >= self.A[R]):
w, o = L, R
else:
w, o = R, L
self.A[v], self.B[v], self.E[v] = self.A[w], self.B[w], self.E[w]
m = min(self.melt[L], self.melt[R])
if not self.E[w] and not self.E[o] and self.A[o] > self.A[w]:
p, q = self.B[w] - self.B[o], self.A[o] - self.A[w]
m = min(m, -((-p) // q)) # ceil(p / q): first t with o(t) >= w(t)
self.melt[v] = m
def _update(self, v, l, r, pos, a, b, empty):
if l == r:
self.A[v], self.B[v], self.E[v], self.melt[v] = a, b, empty, INF
return
m = (l + r) // 2
if pos <= m:
self._update(2 * v, l, m, pos, a, b, empty)
else:
self._update(2 * v + 1, m + 1, r, pos, a, b, empty)
self._pull(v)
def _heat(self, v, l, r):
if self.melt[v] > self.T: # nothing changes in this subtree
return
m = (l + r) // 2
self._heat(2 * v, l, m)
self._heat(2 * v + 1, m + 1, r)
self._pull(v)
def _query(self, v, l, r, ql, qr):
if qr < l or r < ql:
return NEG
if ql <= l and r <= qr:
return self._val(v)
m = (l + r) // 2
return max(self._query(2 * v, l, m, ql, qr),
self._query(2 * v + 1, m + 1, r, ql, qr))
def update(self, i, a, b):
self._update(1, 1, self.n, i, a, b, False)
def heaten(self, t):
assert t >= self.T
self.T = t
self._heat(1, 1, self.n)
def query(self, l, r):
return self._query(1, 1, self.n, l, r)
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
pos = 2
st = KineticSegTree(n)
for i in range(1, n + 1):
st.update(i, int(data[pos]), int(data[pos + 1]))
pos += 2
out = []
for _ in range(q):
typ = data[pos]
if typ == b'1':
st.update(int(data[pos + 1]), int(data[pos + 2]), int(data[pos + 3]))
pos += 4
elif typ == b'2':
st.heaten(int(data[pos + 1]))
pos += 2
else:
out.append(st.query(int(data[pos + 1]), int(data[pos + 2])))
pos += 3
if out:
print("\n".join(map(str, out)))
main()
Muốn lấy min thay vì max: lưu rồi đổi dấu kết quả. Muốn "xoá" một vị trí: gọi erase(i) (bản C++), lá trở thành rỗng với giá trị . Với , hệ số góc tới , tung độ gốc tới , bản C++ chạy khoảng 0.2 giây.
Độ phức tạp
| Thao tác | Thời gian | Lý do |
|---|---|---|
Dựng cây ( lần update) |
mỗi lần tính lại một đường từ lá lên gốc | |
update(i, a, b) |
sửa lá rồi pull tổ tiên, mỗi pull |
|
query(l, r) |
nút phủ đoạn, giá trị mỗi nút tính tại trong | |
heaten(t) |
khấu hao | mỗi lần đổi người thắng tốn một đường ; số lần đổi được khấu hao mỗi thao tác (xem phần trực giác về cận và giả thiết) |
Bộ nhớ: , mỗi nút lưu một đường thẳng và một số melt (mảng nút). Đệ quy chỉ sâu .
Lưu ý heaten có thể thăm nhiều nút trong một lần gọi (ví dụ thời gian nhảy rất xa làm nhiều trận đổi kết quả cùng lúc), nhưng tổng trên cả dãy thao tác vẫn bị chặn như trên.
⚠️ Lỗi thường gặp
- Cho thời gian đi lùi. Toàn bộ lý luận dựa trên "người thắng chỉ đổi sang đường dốc hơn". Nếu giảm, các nút có melt vẫn có thể sai mà
heatenkhông đi vào sửa. Truy vấn với tuỳ ý phải dùng Li Chao Tree hoặc xử lý offline (sắp truy vấn theo tăng dần). - Tràn số khi tính giao điểm hoặc giá trị. và hiệu phải dùng
long long; với , là đã sát . Nếu lớn hơn, dùng__int128khi tính. Giá trị "rỗng"NEGđừng đặt bằngLLONG_MINvì cộng/trừ sẽ tràn, dùngLLONG_MIN / 4và kiểm tra cờemptytrước khi tính giao điểm. - Làm tròn sai thời điểm đuổi kịp. Phép chia nguyên trong C++ làm tròn về 0, nên với tử số âm
p / qkhông phải floor. Dùng hàmceilDivxử lý cả số âm (hoặc-((-p) // q)trong Python). Nếu dùng floor thay vì ceil, melt có thể nhỏ hơn hoặc bằng ngay sau khi tính, vi phạm bất biến. - Xử lý hòa không nhất quán. Khi hai đường bằng nhau tại , phải chọn đường có hệ số góc lớn hơn (nó sẽ dẫn trước ở mọi ). Nếu chọn đường thoải hơn, tính ra bằng đúng , tức melt , phá bất biến "melt ":
heatengọi lại với cùng sẽ thăm lại các nút đó, và cài đặt nào dùng điều kiện so sánh khác (ví dụmelt < T) sẽ bỏ sót thay đổi. - Quên lấy min melt của hai con. Nếu chỉ tính từ trận đấu tại ,
heatensẽ dừng ở dù bên dưới đã có trận đổi kết quả, và người thắng ở các nút con trở nên sai. - Nghĩ KST là cho mọi thao tác. Một lần
heatenđơn lẻ có thể tốn ; chỉ có cận khấu hao. Đừng dùng KST khi cần đảm bảo thời gian tệ nhất cho từng thao tác (ví dụ bài tương tác có giới hạn mỗi truy vấn).
Biến thể / Mở rộng
So sánh với Li Chao Tree và Convex Hull Trick
| CHT (ngăn xếp / deque) | Li Chao Tree | Kinetic Segment Tree | |
|---|---|---|---|
| Điểm truy vấn | đơn điệu (hoặc tìm kiếm nhị phân) | tuỳ ý | chỉ tăng |
| Thứ tự thêm đường | hệ số góc đơn điệu | tuỳ ý | tuỳ ý |
| Xoá / sửa đường | không | không (bản thường) | có, |
| Truy vấn trên đoạn chỉ số | không | phải lồng cây, | có, |
| Độ phức tạp | khấu hao | mỗi thao tác | query/update, khấu hao heaten |
Nói gọn: Li Chao mạnh khi điểm hỏi tuỳ ý nhưng tập đường chỉ được thêm; KST đánh đổi "điểm hỏi tuỳ ý" lấy khả năng sửa đường và hỏi theo đoạn chỉ số. Bao lồi đơn điệu trong Tối ưu quy hoạch động là trường hợp riêng khi mọi thứ đều đơn điệu.
Ứng dụng điển hình
- Mỗi phần tử lớn lên với tốc độ riêng. Cây cao và mỗi ngày cao thêm ; các truy vấn: "sau ngày , cây cao nhất trong đoạn ", "chặt cây và trồng cây mới" (
update). Đúng nguyên mẫu KST. - Quy hoạch động với điểm hỏi tăng dần. : đặt đường vào vị trí ngay khi tính xong , rồi với mỗi gọi
heaten(j)và lấy min trên . Hệ số góc không cần đơn điệu, và nếu đề giới hạn trong một cửa sổ thì chỉ cần đổi đoạn truy vấn. - Truy vấn offline với tham số tuỳ ý. Nếu mỗi truy vấn hỏi với bất kỳ, sắp các truy vấn theo tăng dần rồi
heaten(c)lần lượt, biến bài toán thành dạng thời gian chỉ tăng. Thời điểm ban đầu đặt bằng giá trị nhỏ nhất (có thể âm).
heaten theo đoạn
Biến thể mạnh hơn cho phép heaten(l, r, d): chỉ các vị trí trong "trôi thời gian" thêm (mỗi lá có thời gian riêng, tương đương cộng vào ). Cài đặt cần thẻ lazy cộng thời gian, giống Segment Tree Beats ở chỗ chỉ đi xuống khi melt của nút bị vượt. Cận đã biết cho biến thể này là khấu hao mỗi thao tác, nhưng cài đặt và lý luận phức tạp hơn đáng kể.
Bài tập luyện
- Thay đổi dữ liệu (dhbb23_hkdata) (Rất khó) Mỗi giả định cần và của trên đoạn với tuỳ ý: sắp giả định theo tăng dần rồi dùng hai KST (một cho max, một cho min với đường đổi dấu) trả lời truy vấn đoạn.
- Mua thuyền (chtline) (Rất khó) DP với không đơn điệu và điểm hỏi tăng dần: thêm đường vào vị trí rồi
heaten(j), thay thế được Li Chao Tree.
(Ghi chú: hiện chưa có bài trên CTOJ được gắn nhãn kinetic segment tree. Hai bài trên là các bài có lời giải chính khác (bao lồi trên cây phân đoạn, Li Chao) nhưng giải đúng mô hình "max/min đường thẳng, thời gian chỉ tăng" của KST.)
Bình luận