Wiki › Cấu trúc dữ liệu › Sqrt Tree (truy vấn đoạn O(1))

Sqrt Tree (truy vấn đoạn O(1))

Sqrt Tree trả lời truy vấn đoạn cho mọi phép kết hợp (tích ma trận, tích modulo, top-2...) trong O(1) sau O(n log log n) tiền xử lý, không cần idempotent như Sparse Table.

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

Sqrt Tree là cấu trúc dữ liệu trả lời truy vấn đoạn al∘al+1∘…∘ar trên mảng tĩnh trong O(1) mỗi truy vấn, với phép ∘ chỉ cần kết hợp (associative): tổng, tích modulo, nhân ma trận, hợp hàm, ghép xâu, "hai giá trị lớn nhất"... Tiền xử lý tốn O(nloglogn) thời gian và bộ nhớ. So với cách ngây thơ O(n) mỗi truy vấn, Segment Tree O(logn) mỗi truy vấn, hay Sparse Table O(1) nhưng chỉ với phép idempotent, Sqrt Tree vừa nhanh vừa tổng quát.

Bảng so sánh nhanh (mảng tĩnh, n phần tử, phép kết hợp ∘):

Cấu trúc Tiền xử lý Truy vấn Điều kiện trên ∘
Sparse Table O(nlogn) O(1) kết hợp và idempotent (min, max, gcd, AND, OR)
Disjoint Sparse Table O(nlogn) O(1) chỉ cần kết hợp
Segment Tree O(n) O(logn) chỉ cần kết hợp (có cập nhật)
Chia căn hai tầng O(n) O(n) chỉ cần kết hợp
Sqrt Tree O(nloglogn) O(1) chỉ cần kết hợp

Ý tưởng / Trực giác

Bước 1: chia căn, nhưng trả lời bằng ba mảnh

Chia mảng thành các khối liên tiếp dài khoảng n. Với mỗi khối, tính sẵn:

  • pref[j]: tích (theo ∘) từ đầu khối chứa j đến j;
  • suf[j]: tích từ j đến cuối khối chứa j;
  • between[x][y]: tích của trọn các khối x,x+1,…,y.

Có khoảng n khối nên bảng between có (n)2=n ô, mỗi ô tính O(1) từ ô bên trái: between[x][y]=between[x][y−1]∘khốiy.

Nếu l và r nằm ở hai khối khác nhau bl<br thì đoạn [l,r] tách đúng thành ba mảnh không chồng nhau, theo đúng thứ tự từ trái sang phải:

al∘…∘ar=suf[l]∘between[bl+1][br−1]∘pref[r]

(mảnh giữa bỏ qua nếu bl+1>br−1). Vì ba mảnh rời nhau, không phần tử nào bị tính hai lần, nên không cần idempotent; vì giữ đúng thứ tự trái sang phải, không cần giao hoán. Chỉ cần kết hợp để được phép "đặt ngoặc" tùy ý.

Bước 2: còn trường hợp l,r cùng khối thì sao?

Đây là chỗ chia căn thường phải quét tay O(n). Sqrt Tree xử lý bằng đệ quy: mỗi khối dài n lại được xây một tầng y hệt (chia thành khối con dài n1/4, có pref/suf/between riêng), rồi khối con lại xây tiếp, ... Độ dài khối giảm theo n→n1/2→n1/4→…, nên sau O(loglogn) tầng khối chỉ còn dài 2.

Một truy vấn chỉ cần dùng đúng một tầng: tầng đầu tiên (từ trên xuống) mà l và r nằm cùng một khối nhưng khác khối con. Ở tầng đó công thức ba mảnh ở trên cho đáp án ngay.

Bước 3: tìm tầng đúng trong O(1) bằng bit cao nhất khác nhau

Nếu cứ đi từ tầng trên xuống để tìm tầng phù hợp thì mất O(loglogn). Mẹo: làm tròn n lên lũy thừa của 2, N=2K, và chọn mọi kích thước khối là lũy thừa của 2. Ở một tầng có khối dài 2k và khối con dài 2s (s=⌈k/2⌉):

  • l,r cùng khối ⟺ l và r giống nhau ở mọi bit từ k trở lên;
  • l,r khác khối con ⟺ chúng khác nhau ở ít nhất một bit từ s trở lên.

Gọi h là bit cao nhất mà l và r khác nhau, tức h=⌊log2(l⊕r)⌋ (một lệnh __builtin_clz). Hai điều kiện trên tương đương với s≤h<k. Các tầng có (k,s)=(K,⌈K/2⌉),(⌈K/2⌉,…),…,(2,1) nên các khoảng [s,k) phủ kín và rời nhau trên [1,K). Ta tính sẵn mảng layerOf[h] và tra trong O(1). Riêng h=0 nghĩa là r=l+1, trả về al∘ar trực tiếp.

Ví dụ chạy tay

Lấy phép ∘ là ghép xâu (kết hợp nhưng không giao hoán, không idempotent), mảng 16 chữ cái, chỉ số từ 0:

array base=0
a b c d e f g h i j k l m n o p
ranges 0..3 4..7 8..11 12..15

N=16=24, nên có hai tầng:

Tầng Khối dài Khối con dài Dùng khi bit h
0 24=16 22=4 h∈{2,3}
1 22=4 21=2 h=1
(trực tiếp) h=0

Bảng của tầng 0 (4 khối con abcd | efgh | ijkl | mnop):

j       :  0     1     2     3     4     5     6     7    ...  12    13    14    15
pref[j] :  a     ab    abc   abcd  e     ef    efg   efgh ...  m     mn    mno   mnop
suf[j]  :  abcd  bcd   cd    d     efgh  fgh   gh    h    ...  mnop  nop   op    p

between[x][y] (x <= y):
        y=0     y=1        y=2            y=3
x=0     abcd    abcdefgh   abcdefghijkl   abcdefghijklmnop
x=1             efgh       efghijkl       efghijklmnop
x=2                        ijkl           ijklmnop
x=3                                       mnop

Truy vấn [1,13]. 1=00012, 13=11012, 1⊕13=11002, bit cao nhất h=3 nên dùng tầng 0. Khối con của l là bl=1≫2=0, của r là br=13≫2=3.

array base=0
a b c d e f g h i j k l m n o p
highlight orange 1..3
highlight blue 4..11
highlight green 12..13
pointer l 1
pointer r 13
label 2 suf[1]
label 7 between[1][2]
label 12 pref[13]

bcd⏟suf[1]∘efghijkl⏟between[1][2]∘mn⏟pref[13]=bcdefghijklmn

Đúng là đoạn a1..a13, chỉ với 2 phép ∘.

Truy vấn [2,6]. 00102⊕01102=01002, h=2, vẫn tầng 0. bl=0, br=1 kề nhau nên không có mảnh giữa: suf[2]∘pref[6]=cd∘efg=cdefg.

Truy vấn [8,10]. 10002⊕10102=00102, h=1: l và r cùng khối con của tầng 0 (ijkl), nên xuống tầng 1. Ở tầng 1, khối ijkl được chia thành khối con ij | kl:

tầng 1, khối 8..11:   j      : 8    9    10   11
                      pref[j]: i    ij   k    kl
                      suf[j] : ij   j    kl   l

Đáp án suf1[8]∘pref1[10]=ij∘k=ijk.

Truy vấn [4,5]. 01002⊕01012=00012, h=0: hai phần tử kề nhau, trả a4∘a5=ef.

Tất cả kết quả trên đã được kiểm tra bằng chương trình bên dưới (thay phép nhân ma trận bằng ghép xâu).

Cài đặt

Phiên bản C++ là Sqrt Tree đầy đủ, viết dạng template nhận phép ∘ bất kỳ. Ví dụ dùng tích ma trận 2×2 modulo 109+7: phép này kết hợp nhưng không giao hoán, không idempotent và không có nghịch đảo tổng quát, nên Sparse Table và "tích tiền tố chia ngược" đều bó tay.

Phiên bản Python là bản hai tầng đơn giản (chia căn + pref/suf/between): truy vấn qua nhiều khối O(1), truy vấn nằm gọn trong một khối thì quét O(n). Thường đủ dùng và dễ cài hơn nhiều.

Định dạng vào: dòng đầu n,q; n dòng mỗi dòng 4 số là ma trận (abcd); q dòng mỗi dòng l,r (từ 1). In ra 4 phần tử của tích MlMl+1⋯Mr.

C++
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1'000'000'007;

// Example non-commutative associative operation: 2x2 matrix product mod p.
struct Mat {
    long long a[2][2];
};
Mat mul(const Mat& x, const Mat& y) {
    Mat z;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            z.a[i][j] = (x.a[i][0] * y.a[0][j] + x.a[i][1] * y.a[1][j]) % MOD;
    return z;
}

// Sqrt tree: O(n log log n) build, O(1) query for any associative op.
template <class T, T (*op)(const T&, const T&)>
struct SqrtTree {
    int n, LOG;
    vector<T> a;
    vector<int> blkBits, subBits;          // per layer: block size 2^k, sub-block size 2^s
    vector<int> layerOf;                   // layerOf[h] = layer used when highest differing bit is h
    vector<vector<T>> pref, suf, between;

    SqrtTree(const vector<T>& v) : n(v.size()) {
        LOG = 1;
        while ((1 << LOG) < n) LOG++;
        int N = 1 << LOG;
        a = v;
        a.resize(N, v[0]);                 // padding is never read by a valid query
        layerOf.assign(LOG, -1);
        for (int k = LOG; k >= 2; k = (k + 1) / 2) {
            int s = (k + 1) / 2;
            for (int h = s; h < k; h++) layerOf[h] = blkBits.size();
            blkBits.push_back(k);
            subBits.push_back(s);
        }
        int L = blkBits.size();
        pref.assign(L, vector<T>(N));
        suf.assign(L, vector<T>(N));
        between.resize(L);
        for (int i = 0; i < L; i++) build(i, N);
    }

    void build(int i, int N) {
        int k = blkBits[i], s = subBits[i];
        int sub = 1 << s, cnt = 1 << (k - s);   // cnt sub-blocks per block
        vector<T>& P = pref[i];
        vector<T>& S = suf[i];
        for (int st = 0; st < N; st += sub) {
            P[st] = a[st];
            for (int j = st + 1; j < st + sub; j++) P[j] = op(P[j - 1], a[j]);
            S[st + sub - 1] = a[st + sub - 1];
            for (int j = st + sub - 2; j >= st; j--) S[j] = op(a[j], S[j + 1]);
        }
        // between[blk*cnt*cnt + x*cnt + y] = op of sub-blocks x..y inside block blk
        between[i].resize((size_t)(N >> k) * cnt * cnt);
        for (int blk = 0; blk < (N >> k); blk++) {
            size_t base = (size_t)blk * cnt * cnt;
            int start = blk << k;
            for (int x = 0; x < cnt; x++) {
                T cur = S[start + (x << s)];   // whole sub-block x = suffix from its first cell
                between[i][base + x * cnt + x] = cur;
                for (int y = x + 1; y < cnt; y++) {
                    cur = op(cur, S[start + (y << s)]);
                    between[i][base + x * cnt + y] = cur;
                }
            }
        }
    }

    // op(a[l], ..., a[r]), 0-based, l <= r
    T query(int l, int r) const {
        if (l == r) return a[l];
        int h = 31 - __builtin_clz(l ^ r);
        if (h == 0) return op(a[l], a[r]);   // r == l + 1
        int i = layerOf[h];
        int k = blkBits[i], s = subBits[i], cnt = 1 << (k - s);
        int bl = (l >> s) & (cnt - 1), br = (r >> s) & (cnt - 1);
        T res = suf[i][l];
        if (bl + 1 < br) {
            size_t base = (size_t)(l >> k) * cnt * cnt;
            res = op(res, between[i][base + (bl + 1) * cnt + (br - 1)]);
        }
        return op(res, pref[i][r]);
    }
};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<Mat> v(n);
    for (auto& m : v) scanf("%lld %lld %lld %lld", &m.a[0][0], &m.a[0][1], &m.a[1][0], &m.a[1][1]);
    SqrtTree<Mat, mul> st(v);
    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);               // 1-based
        Mat m = st.query(l - 1, r - 1);
        printf("%lld %lld %lld %lld\n", m.a[0][0], m.a[0][1], m.a[1][0], m.a[1][1]);
    }
}
Python
import sys
from math import isqrt

MOD = 10**9 + 7


def mul(x, y):
    # 2x2 matrix product mod p, matrices stored as tuples (a, b, c, d)
    a, b, c, d = x
    e, f, g, h = y
    return ((a * e + b * g) % MOD, (a * f + b * h) % MOD,
            (c * e + d * g) % MOD, (c * f + d * h) % MOD)


class TwoLevelSqrt:
    """Two-level version: O(n) build, O(1) query across blocks,
    O(sqrt n) query when l and r fall in the same block."""

    def __init__(self, a, op):
        self.a, self.op = a, op
        n = len(a)
        self.b = b = max(1, isqrt(n))           # block size
        self.nb = nb = (n + b - 1) // b         # number of blocks
        self.pref = [None] * n
        self.suf = [None] * n
        whole = []
        for s in range(0, n, b):
            e = min(n, s + b)
            cur = a[s]
            self.pref[s] = cur
            for j in range(s + 1, e):
                cur = op(cur, a[j])
                self.pref[j] = cur
            cur = a[e - 1]
            self.suf[e - 1] = cur
            for j in range(e - 2, s - 1, -1):
                cur = op(a[j], cur)
                self.suf[j] = cur
            whole.append(self.suf[s])
        # between[x][y] = op of whole blocks x..y
        self.between = [[None] * nb for _ in range(nb)]
        for x in range(nb):
            cur = whole[x]
            self.between[x][x] = cur
            for y in range(x + 1, nb):
                cur = op(cur, whole[y])
                self.between[x][y] = cur

    def query(self, l, r):  # 0-based, inclusive
        bl, br = l // self.b, r // self.b
        if bl == br:                            # same block: scan directly
            res = self.a[l]
            for j in range(l + 1, r + 1):
                res = self.op(res, self.a[j])
            return res
        res = self.suf[l]
        if bl + 1 < br:
            res = self.op(res, self.between[bl + 1][br - 1])
        return self.op(res, self.pref[r])


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    vals = list(map(int, data[2:2 + 4 * n]))
    a = [tuple(vals[4 * i:4 * i + 4]) for i in range(n)]
    st = TwoLevelSqrt(a, mul)
    out = []
    pos = 2 + 4 * n
    for _ in range(q):
        l, r = int(data[pos]) - 1, int(data[pos + 1]) - 1
        pos += 2
        out.append(" ".join(map(str, st.query(l, r))))
    print("\n".join(out))


if __name__ == "__main__":
    main()

Ví dụ chạy (cả hai chương trình cho cùng kết quả):

Input:
5 4
1 1 1 0
2 0 0 1
1 1 0 1
0 1 1 0
3 0 1 1
1 5
2 3
3 4
4 4

Output:
11 2 8 2
2 2 0 1
1 1 1 0
0 1 1 0

Kiểm tra tay truy vấn [2,3]: (2001)(1101)=(2201). Nếu nhân ngược thứ tự sẽ ra (2101), khác hẳn: đó là lý do suf phải tính aj∘suf[j+1] (phần tử mới đứng bên trái).

Cả hai cài đặt đã được đối chiếu với cách nhân trực tiếp trên hàng nghìn mảng ngẫu nhiên (n≤300, mọi cặp (l,r)), với cả phép nhân ma trận lẫn phép ghép xâu. Bản C++ dựng với n=2·105 ma trận và trả lời 106 truy vấn trong khoảng 0,25 giây.

Độ phức tạp

  • Số tầng. Số mũ khối giảm k→⌈k/2⌉, bắt đầu từ K=⌈log2n⌉ và dừng khi k<2, nên có O(logK)=O(loglogn) tầng. Với n=2·105 (K=18): các tầng có k=18,9,5,3,2, tức chỉ 5 tầng.
  • Tiền xử lý mỗi tầng O(N). pref và suf: mỗi ô một phép ∘, tổng 2N. between: mỗi khối dài 2k có c=2k−s khối con, bảng c2=22⌊k/2⌋≤2k ô, cộng trên N/2k khối được ≤N ô, mỗi ô một phép ∘.
  • Tổng tiền xử lý: O(NloglogN)=O(nloglogn) thời gian và bộ nhớ (N<2n).
  • Truy vấn O(1): một __builtin_clz, một lần tra layerOf, vài phép dịch bit và tối đa 2 phép ∘. Không có vòng lặp nào.
  • Bản Python hai tầng: dựng O(n) (bảng between có (n/b)2≈n ô), truy vấn O(1) khi l,r khác khối và O(n) khi cùng khối.

Nếu bản thân phép ∘ tốn C (vd nhân ma trận m×m tốn m3), nhân mọi con số trên với C, và bộ nhớ nhân với kích thước một phần tử.

⚠️ Lỗi thường gặp

  • Đảo thứ tự với phép không giao hoán. Viết S[j] = op(S[j+1], a[j]) hoặc ghép ba mảnh theo thứ tự pref, between, suf cho kết quả sai với nhân ma trận, ghép xâu, hợp hàm, nhưng vẫn đúng với tổng hay tích số, nên test bằng tổng không phát hiện được. Cách tránh: luôn giữ thứ tự trái sang phải, và test với một phép không giao hoán như ghép xâu.
  • Dùng mẹo hai đoạn chồng nhau của Sparse Table. Với phép không idempotent (tổng, tích, top-2, ma trận), phần chồng bị tính hai lần. Triệu chứng: tổng bị cộng đôi, "hai số lớn nhất" ra cùng một phần tử hai lần. Đó chính là lý do cần Sqrt Tree hoặc Disjoint Sparse Table.
  • Tưởng tích tiền tố + nghịch đảo là đủ. ∏lr=Pr·Pl−1−1 chỉ đúng khi mọi phần tử khả nghịch: hỏng khi có ai≡0(modp), khi modulo không nguyên tố, khi ma trận suy biến, hay với phép như max của tổng. Sqrt Tree không cần nghịch đảo.
  • Quên trường hợp h=0 và l=r. Ở tầng cuối k=2, s=1, nên layerOf[0] không có tầng nào (−1 trong code). Bỏ hai dòng if đầu query sẽ đọc layerOf[0] = -1 và truy cập ngoài mảng; còn l=r thì __builtin_clz(0) là hành vi không xác định.
  • Không làm tròn n lên lũy thừa của 2. Mẹo "bit cao nhất khác nhau" chỉ đúng khi mọi khối bắt đầu ở bội của kích thước khối và kích thước là lũy thừa của 2. Giá trị độn thêm ở cuối (code dùng a0) không bao giờ được đọc với truy vấn r<n, vì mọi mảnh dùng đến đều nằm trong [l,r].
  • Bộ nhớ với phần tử lớn. Mỗi tầng giữ 2N ô pref/suf và tối đa N ô between: với n=2·105 (N=218, 5 tầng) code trên giữ khoảng 3,5·106 phần tử. Với ma trận 2×2 kiểu long long (32 byte) là khoảng 110 MB; nếu giới hạn chặt, lưu phần tử bằng int (giá trị <109+7) và chỉ ép long long khi nhân, hoặc dùng bản hai tầng.
  • Tràn số khi nhân modulo. (a·e+b·g) với a,e,b,g<109+7 là khoảng 2·1018, vẫn vừa long long (tối đa ≈9,2·1018), nhưng cộng thêm hạng tử thứ ba (ma trận 3×3) mà không lấy modulo giữa chừng thì có thể tràn.

Biến thể / Mở rộng

  • Disjoint Sparse Table. Cùng ý tưởng "suf của nửa trái ∘ pref của nửa phải", nhưng chia đôi đệ quy thay vì chia căn: ở mức k, mảng chia thành khối dài 2k+1, mỗi khối lưu suffix của nửa trái và prefix của nửa phải. Truy vấn chọn mức theo bit cao nhất của l⊕r, ghép đúng 2 mảnh. Cài ngắn hơn Sqrt Tree nhưng tốn O(nlogn) bộ nhớ thay vì O(nloglogn). Trên thực tế với n≤106 hai con số khá gần nhau (khoảng 2·107 ô so với khoảng 1,4·107 ô của cài đặt trên), nên Disjoint Sparse Table thường là lựa chọn gọn hơn khi bộ nhớ không quá chặt.
  • Cập nhật điểm. Gán ai←x thì ở mỗi tầng chỉ khối con chứa i phải tính lại pref/suf, nhưng bảng between ở tầng trên cùng có O(n) ô bị ảnh hưởng. Kỹ thuật chuẩn (xem cp-algorithms) thay bảng between tầng trên cùng bằng một Sqrt Tree nhỏ dựng trên n giá trị "trọn khối", đưa cập nhật điểm về O(n) mà truy vấn vẫn O(1). Nếu cập nhật nhiều, Segment Tree O(logn) cho cả hai thao tác thường là lựa chọn hợp lý hơn.
  • Khi nào thực sự cần. Với q≤2·105, Segment Tree hay bản chia căn hai tầng thường đã đủ nhanh. Sqrt Tree đáng giá khi q rất lớn (cỡ 106 đến 107 truy vấn trực tuyến) trên mảng tĩnh, hoặc khi phép ∘ đắt (ma trận) nên muốn số phép ∘ mỗi truy vấn là hằng số.
  • Phép thường gặp. Tích ma trận (đếm đường đi, quy hoạch động tuyến tính trên đoạn, xem Lũy thừa ma trận), hợp các hàm tuyến tính x↦ax+b, "hai giá trị lớn nhất theo vị trí", tổng đoạn con lớn nhất (lưu bộ 4 giá trị: tổng, max tiền tố, max hậu tố, max đoạn con).
  • Truy vấn offline. Nếu được đọc trước mọi truy vấn, chia để trị (gom truy vấn đi qua điểm giữa) cũng cho O((n+q)logn) với O(n) bộ nhớ; xem thêm Thuật toán Mo cho các truy vấn không có phép kết hợp đẹp.

Bài tập luyện

Kho bài CTOJ hiện chưa có bài nào bắt buộc phải dùng Sqrt Tree (giới hạn thường đủ rộng cho Sparse Table hoặc Segment Tree). Các bài dưới đây là truy vấn đoạn tĩnh, giải được trọn vẹn bằng Sqrt Tree; hai bài sau dùng phép gộp không idempotent, đúng chỗ mạnh của cấu trúc này.

  • RMQ tĩnh, min đoạn (rmqspar) (Dễ) Bài khởi động: thay mul bằng min để kiểm tra cài đặt Sqrt Tree trên N,Q=2·105, rồi so với Sparse Table.
  • Điền phiếu (dhbb25dx2811_dienphieu) (Trung bình) Max đoạn với Q=2·105 truy vấn trên mảng tĩnh; luyện đọc nhanh và trả lời O(1) mỗi truy vấn.
  • Dữ liệu (dhbb23_rdat) (Trung bình) Đáp án quy về tổng hai giá trị lớn nhất theo vị trí trong đoạn; phép gộp "top-2" không idempotent, nên dùng hai đoạn chồng nhau sẽ đếm một phần tử hai lần, còn ba mảnh rời nhau của Sqrt Tree thì không.
  • Mã hóa (dhbb25dx4310_mahoa) (Trung bình) Tích lớn nhất của hai phần tử trong đoạn, quy về hai số lớn nhất và hai số nhỏ nhất; phần tử của cấu trúc là một bộ 4 giá trị với phép gộp kết hợp nhưng không idempotent.
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