Wiki › Cấu trúc dữ liệu › Cây › Kinetic Segment Tree

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).

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 20 phút 4 lượt xem

Kinetic Segment Tree (KST, cây phân đoạn "động học") giải bài toán sau: có N vị trí, vị trí i giữ một hàm bậc nhất fi(t)=ai·t+bi (hiểu là phần tử i có giá trị ban đầu bi và lớn lên với tốc độ riêng ai). Ta cần hỗ trợ ba thao tác:

  • update(i, a, b): thay hàm ở vị trí i bằng a·t+b;
  • heaten(t): cho thời gian trôi tới t, với điều kiện t không bao giờ giảm;
  • query(l, r): trả về maxl≤i≤rfi(t) tại thời điểm hiện tại.

Cách ngây thơ tốn O(r−l+1) 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 O(logN), còn heaten tốn O(log2N) 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 v phụ trách đoạn [l,r] và lưu đường thẳng thắng wv, tức hàm có giá trị lớn nhất trong đoạn tại thời điểm hiện tại T. 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 T 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 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 v, người thắng là w và người thua là o:

  • Nếu ao≤aw thì o không bao giờ vượt được w nữa (đang thua, lại tăng chậm hơn hoặc bằng).
  • Nếu ao>aw thì o đuổi kịp w tại thời điểm đầu tiên t có aot+bo≥awt+bw, tức tc=⌈bw−boao−aw⌉.
Thời điểm tan chảy

Gọi melt(v) là thời điểm sớm nhất mà bất kỳ trận đấu nào trong cây con của v đổi kết quả: melt(v)=min(melt(con trái), melt(con phải), tc(v)), với tc(v)=+∞ khi người thua ở v không thể vượt. Lá có melt=+∞.

Bất biến: mọi nút đều có melt(v)>T. Khi đó người thắng ở mọi nút vẫn đúng tại thời điểm T, nên query chỉ cần lấy max giá trị tại T của các nút phủ [l,r], y hệt cây phân đoạn thường.

heaten: chỉ đi vào chỗ đã tan

Khi heaten(t) đặt T=t, những nút có melt(v)≤T có thể đã sai. Ta đi từ gốc: nếu melt(v)>T 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 v (chọn lại người thắng tại T, 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ừ w sang o thì ao>aw: 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 k vị trí đổi người thắng tối đa k−1 lần, tổng trên mọi nút là O(NlogN) lần, mỗi lần được phát hiện bằng một đường đi dài O(logN) từ gốc. Không có cập nhật, toàn bộ quá trình heaten tốn O(Nlog2N).

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" O(logN) 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 O(log2N) 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à O(log2N·α(N)) (dựa trên dãy Davenport-Schinzel), còn O(log2N) được tin là đúng và chạy nhanh như vậy trong thực tế.

Ví dụ chạy tay

N=4 hàm, thời điểm bắt đầu T=0:

Vị trí Hàm t=0 t=2 t=4 t=6
1 f1=6 6 6 6 6
2 f2=t+3 3 5 7 9
3 f3=2t 0 4 8 12
4 f4=8−t 8 6 4 2

Cây phân đoạn có 7 nút: gốc 1 phụ trách [1,4], nút 2 phụ trách [1,2], nút 3 phụ trách [3,4], 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 (T=0):

Nút Thắng Thua Thua đuổi kịp? tc melt
2 [1,2] f1 (6) f2 (3) 1>0, có ⌈(6−3)/(1−0)⌉=3 3
3 [3,4] f4 (8) f3 (0) 2>−1, có ⌈(8−0)/(2+1)⌉=⌈8/3⌉=3 3
1 [1,4] f4 (8) f1 (6) 0>−1, có ⌈(8−6)/(0+1)⌉=2 min(3,3,2)=2

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 T Kết quả Kiểm tra trực tiếp
query(1, 4) 0 8 max(6,3,0,8)
heaten(2), query(1, 4) 2 6 max(6,5,4,6)
heaten(4), query(1, 2) 4 7 max(6,7)
heaten(6), update(4, 3, -5), query(1, 4) 6 13 max(6,9,12,13)
query(1, 3) 6 12 max(6,9,12)

Để ý heaten(6) không thăm nút nào: sau t=4 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 N, Q, rồi N cặp ai,bi, rồi Q thao tác: 1 i a b (cập nhật), 2 t (heaten, t không giảm), 3 l r (in max). Thời điểm ban đầu là T=0. Hai bản cho cùng output; đã được đối chiếu với brute force O(N) 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
C++
#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));
        }
    }
}
Python
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 (−ai,−bi) 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 N=Q=2·105, hệ số góc tới 106, tung độ gốc tới 1012, 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 (N lần update) O(NlogN) mỗi lần tính lại một đường từ lá lên gốc
update(i, a, b) O(logN) sửa lá rồi pull O(logN) tổ tiên, mỗi pull O(1)
query(l, r) O(logN) O(logN) nút phủ đoạn, giá trị mỗi nút tính tại T trong O(1)
heaten(t) O(log2N) khấu hao mỗi lần đổi người thắng tốn một đường O(logN); số lần đổi được khấu hao O(logN) mỗi thao tác (xem phần trực giác về cận và giả thiết)

Bộ nhớ: O(N), mỗi nút lưu một đường thẳng và một số melt (mảng 4N nút). Đệ quy chỉ sâu O(logN).

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 t giảm, các nút có melt >T vẫn có thể sai mà heaten không đi vào sửa. Truy vấn với t tuỳ ý phải dùng Li Chao Tree hoặc xử lý offline (sắp truy vấn theo t tăng dần).
  • Tràn số khi tính giao điểm hoặc giá trị. a·t+b và hiệu bw−bo phải dùng long long; với |a|≤109, |t|≤109 là đã sát 1018. Nếu lớn hơn, dùng __int128 khi tính. Giá trị "rỗng" NEG đừng đặt bằng LLONG_MIN vì cộng/trừ sẽ tràn, dùng LLONG_MIN / 4 và kiểm tra cờ empty trướ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 / q không phải floor. Dùng hàm ceilDiv xử 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 T 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 T, phải chọn đường có hệ số góc lớn hơn (nó sẽ dẫn trước ở mọi t>T). Nếu chọn đường thoải hơn, tc tính ra bằng đúng T, tức melt =T, phá bất biến "melt >T": heaten gọi lại với cùng T 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 melt(v) chỉ tính từ trận đấu tại v, heaten sẽ dừng ở v 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à O(logN) cho mọi thao tác. Một lần heaten đơn lẻ có thể tốn O(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 t đơ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ó, O(logN)
Truy vấn trên đoạn chỉ số [l,r] không phải lồng cây, O(log2) có, O(logN)
Độ phức tạp O(1) khấu hao O(logV) mỗi thao tác O(logN) query/update, O(log2N) 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 i cao bi và mỗi ngày cao thêm ai; các truy vấn: "sau ngày t, cây cao nhất trong đoạn [l,r]", "chặt cây i 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. dpj=mini<j(dpi+bi+ai(j−i)): đặt đường aix+(dpi+bi−aii) vào vị trí i ngay khi tính xong dpi, rồi với mỗi j gọi heaten(j) và lấy min trên [1,j−1]. Hệ số góc không cần đơn điệu, và nếu đề giới hạn i trong một cửa sổ [j−K,j−1] 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 maxi∈[l,r](Pi+c·i) với c bất kỳ, sắp các truy vấn theo c 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ị c 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 [l,r] "trôi thời gian" thêm d (mỗi lá có thời gian riêng, tương đương cộng ai·d vào bi). 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à O(log3N) 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 max và min của Pi+c·i trên đoạn [u,v] với c tuỳ ý: sắp giả định theo c 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 dpj=mini<j(dpi+bi+ai(j−i)) với ai không đơn điệu và điểm hỏi x=j tăng dần: thêm đường vào vị trí i 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.)

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0