Segment Tree 1D, 2D

Trong nhiều bài toán xử lý dữ liệu, đặc biệt là khi làm việc với mảng hoặc ma trận lớn, chúng ta thường xuyên cần thực hiện hai thao tác cơ bản: cập nhật giá trị tại một vị trí và truy vấn một khoảng giá trị (range query) một cách nhanh chóng. Nếu chỉ sử dụng phương pháp duyệt trực tiếp, thời gian thực thi sẽ tăng vọt khi kích thước dữ liệu lớn. Đó là lúc cấu trúc dữ liệu Segment Tree (cây đoạn) trở nên vô cùng hữu ích: nó cho phép thực hiện cả hai thao tác này trong thời gian logarithmic, đem lại hiệu năng tối ưu. Tiếp theo, chúng ta sẽ tìm hiểu chi tiết về cách xây dựng và ứng dụng Segment Tree 1D cho mảng 1 chiều, cũng như mở rộng lên Segment Tree 2D cho ma trận 2 chiều, giúp giải quyết hiệu quả các bài toán liên quan đến range update và range query.

Mục lục

Segment Tree 1D (Cây Đoạn Thẳng 1 Chiều)

Khái niệm và động lực sử dụng

Vấn đề cơ bản: Giả sử ta có một mảng số nguyên A[0..N−1]. Ta muốn thực hiện hai thao tác chính:

Cập nhật: Thay đổi giá trị tại một vị trí (ví dụ: A[i] = x).
Truy vấn (query): Tính toán một giá trị trên một đoạn con liên tiếp (ví dụ: tổng, giá trị lớn nhất, giá trị nhỏ nhất, v.v.) của mảng, chẳng hạn tính sum(A[L..R]).

Nếu ta thực hiện cập nhật trong O(1) (chỉ gán trực tiếp vào A[i]), nhưng mỗi lần truy vấn đoạn [L..R] mà phải duyệt vòng for từ L đến R thì tốn O(N) trong trường hợp xấu nhất. Với N và số lượng truy vấn, cập nhật lên đến 105 hoặc 106, cách làm “duyệt thẳng” không thể đáp ứng yêu cầu thời gian.

Phương án nhanh hơn: Segment Tree (cây đoạn thẳng) là cấu trúc dữ liệu dạng cây số (tree) được xây dựng trên mảng, giúp ta thực hiện cả hai thao tác cập nhật và truy vấn trong O(log N) (với N là kích thước mảng gốc). Điểm chính: chia mảng thành các đoạn (segment) lồng nhau, lưu trữ thông tin cần thiết (như tổng, max, min, v.v.) cho mỗi đoạn, rồi dùng phép kết hợp (ví dụ cộng) để trả về kết quả cho đoạn bất kỳ.

Cách thiết kế segment tree

Mỗi nút của cây ứng với một đoạn liên tục [l..r] trong mảng.
Nút gốc (root) đại diện cho đoạn toàn mảng [0..N−1].
Với mỗi nút đại diện đoạn [l..r], nếu l < r, ta chia thành hai đoạn con:
Đoạn con trái [l..mid], với mid = (l + r) / 2 (làm tròn xuống).
- Đoạn con phải [mid+1..r].
- Mỗi nút lưu giá trị “tổng” (hoặc max, min, tuỳ bài toán) của toàn bộ phần tử trong đoạn đó. Khi cần truy vấn tổng trên đoạn [L..R], ta đi xuống cây, nếu một nút chứa hoàn toàn trong [L..R], ta trả về giá trị đã lưu ở nút đó; nếu phân mảnh, ta kết hợp kết quả từ hai con.

Cài đặt segment tree 1D bằng C++
Dưới đây minh hoạ một segment tree hỗ trợ:

Xây dựng (build) từ mảng ban đầu.
Cập nhật giá trị tại vị trí idx.
Truy vấn tổng trên đoạn [L..R].

Lưu ý: Chúng ta sẽ dùng cây nhị phân trong mảng. Với mảng gốc độ dài N, ta cấp cho seg kích thước khoảng 4 * N để đảm bảo đủ chỗ lưu các nút.

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

struct SegmentTree {
    int n;                   // Kích thước mảng gốc
    vector<long long> seg;   // Mảng lưu cây, seg[node] lưu tổng của đoạn
    
    // Constructor: khởi tạo cây cho mảng có kích thước _n
    SegmentTree(int _n) {
        n = _n;
        seg.assign(4 * n, 0LL);
    }

    // Hàm xây cây từ mảng A
    // node: chỉ số nút hiện tại trong mảng seg (bắt đầu từ 1)
    // l, r: biên đoạn mà node này đại diện (ban đầu l=0, r=n-1)
    void build(int node, int l, int r, const vector<long long> &A) {
        if (l == r) {
            // Đến lá, lưu giá trị A[l]
            seg[node] = A[l];
            return;
        }
        int mid = (l + r) / 2;
        // Xây cây con trái
        build(2 * node, l, mid, A);
        // Xây cây con phải
        build(2 * node + 1, mid + 1, r, A);
        // Kết hợp hai con (ở đây là tổng)
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }

    // Wrapper để người dùng gọi dễ: chỉ cần truyền vào mảng A
    void build(const vector<long long> &A) {
        build(1, 0, n - 1, A);
    }

    // Hàm cập nhật: gán A[idx] = val
    // node, l, r giống như build
    void update(int node, int l, int r, int idx, long long val) {
        if (l == r) {
            // Đến lá, cập nhật giá trị
            seg[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) {
            // Cập nhật ở cây con trái
            update(2 * node, l, mid, idx, val);
        } else {
            // Cập nhật ở cây con phải
            update(2 * node + 1, mid + 1, r, idx, val);
        }
        // Sau khi cập nhật con, ta phải cập nhật lại nút hiện tại
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }

    // Wrapper để người dùng gọi: update tại idx với giá trị val
    void update(int idx, long long val) {
        update(1, 0, n - 1, idx, val);
    }

    // Hàm truy vấn tổng trên segment [L..R]
    long long query(int node, int l, int r, int L, int R) {
        // Nếu đoạn [l..r] nằm hoàn toàn ngoài [L..R], trả về 0 (phần trung hòa)
        if (r < L || R < l) {
            return 0LL;
        }
        // Nếu đoạn [l..r] nằm hoàn toàn trong [L..R], trả về giá trị nút
        if (L <= l && r <= R) {
            return seg[node];
        }
        // Ngược lại, phân mảnh: truy vấn xuống hai con
        int mid = (l + r) / 2;
        long long leftSum = query(2 * node, l, mid, L, R);
        long long rightSum = query(2 * node + 1, mid + 1, r, L, R);
        return leftSum + rightSum;
    }

    // Wrapper để người dùng gọi: query [L..R]
    long long query(int L, int R) {
        return query(1, 0, n - 1, L, R);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // Tạo và xây cây
    SegmentTree st(N);
    st.build(A);

    // Xử lý Q truy vấn/cập nhật
    // Giả sử: kiểu 1 u v = cập nhật A[u] = v
    //         kiểu 2 L R = truy vấn sum(A[L..R])
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            long long v;
            cin >> u >> v;
            // Giả sử đầu vào u 0-based
            st.update(u, v);
        } else {
            int L, R;
            cin >> L >> R;
            // Giả sử đầu vào L,R 0-based
            long long ans = st.query(L, R);
            cout << ans << "n";
        }
    }
    return 0;
}

Segment Tree 2D (Cây Đoạn Thẳng 2 Chiều)

Khái niệm về segment tree 2D

Bây giờ, ta xét bài toán trên ma trận 2D kích thước N × M (N dòng, M cột). Ta muốn:
1. Cập nhật một phần tử: ví dụ A[x][y] = val (với 0 ≤ x < N, 0 ≤ y < M).
2. Truy vấn một hình chữ nhật con: ví dụ tính tổng các phần tử trong khung con (x1..x2, y1..y2).
Với N, M lên đến 103 (hoặc 105 nếu dạng sparse), cách duyệt trực tiếp qua toàn bộ khung (O(N × M) mỗi lần) quá chậm. Ta có thể mở rộng ý tưởng 1D segment tree sang 2D để hỗ trợ cập nhật và truy vấn bằng O(log N × log M).

Ý tưởng thiết kế segment tree 2D

Cây 2D thực chất là:
- Bên ngoài, ta có một cây theo chỉ số hàng (trục X). Mỗi nút đại diện cho một đoạn hàng [x_l..x_r].
- Mỗi nút đó lại lưu một cây 1D (theo chỉ số cột) để xử lý thông tin “dọc” trong đoạn hàng đó.
Cách tổ chức:
1. Xây cây theo hàng (cây cha):
  - Mỗi nút nodeX lưu một cây 1D seg[nodeX] (thực chất là một vector kích thước ~4*M) biểu diễn thông tin cho các cột trên phần ma trận gồm các hàng trong đoạn [x_l..x_r].
2. Khi xây cây con:
  - Với mỗi nodeX, ta lấy “hai cây 1D của con trái và con phải” rồi kết hợp (merge) để được “cây 1D của nodeX”. Ví dụ, nếu là phép tính tổng, thì với mỗi cột y, ta sẽ gộp sum_left[y] + sum_right[y] để ra sum_nodeX[y].

Cài đặt segment tree 2D bằng C++
Ví dụ: ta muốn xây cây để trả về tổng phần tử trong khung (x1..x2, y1..y2) và hỗ trợ cập nhật.

Giả sử ma trận gốc là A kích thước N × M, khởi tạo với 0 (hoặc từ đầu).

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

struct SegmentTree2D {
    int n, m;                            // n: số dòng, m: số cột
    vector<vector<long long>> seg;      // seg[nodeX] là cây 1D (vector) cho nodeX
    
    // Constructor: khởi tạo cây 2D với kích thước n x m
    SegmentTree2D(int _n, int _m) {
        n = _n;
        m = _m;
        seg.assign(4 * n, vector<long long>(4 * m, 0LL));
    }

    // Hàm build cây 1D tại nodeX, khi build con cho nodeX. 
    // Ở đây, build y cho y-range [yl..yr] trong một nodeX cố định.
    void buildY(int nodeX, int x_l, int x_r, int nodeY, int y_l, int y_r, const vector<vector<long long>> &A) {
        if (y_l == y_r) {
            if (x_l == x_r) {
                // Chỉ một ô duy nhất (x_l, y_l)
                seg[nodeX][nodeY] = A[x_l][y_l];
            } else {
                // Kết hợp 2 con X, cùng cột y_l
                seg[nodeX][nodeY] = seg[nodeX * 2][nodeY] + seg[nodeX * 2 + 1][nodeY];
            }
            return;
        }
        int midY = (y_l + y_r) / 2;
        // Xây con trái Y
        buildY(nodeX, x_l, x_r, nodeY * 2, y_l, midY, A);
        // Xây con phải Y
        buildY(nodeX, x_l, x_r, nodeY * 2 + 1, midY + 1, y_r, A);
        // Kết hợp hai con Y
        seg[nodeX][nodeY] = seg[nodeX][nodeY * 2] + seg[nodeX][nodeY * 2 + 1];
    }

    // Hàm build cây X: iterator chéo qua các node X
    void buildX(int nodeX, int x_l, int x_r, const vector<vector<long long>> &A) {
        if (x_l != x_r) {
            int midX = (x_l + x_r) / 2;
            // Xây cây con X trái
            buildX(nodeX * 2, x_l, midX, A);
            // Xây cây con X phải
            buildX(nodeX * 2 + 1, midX + 1, x_r, A);
        }
        // Sau khi con X đã xong (hoặc chính là lá X), build cây Y cho nodeX
        buildY(nodeX, x_l, x_r, 1, 0, m - 1, A);
    }

    // Wrapper để build toàn bộ
    void build(const vector<vector<long long>> &A) {
        buildX(1, 0, n - 1, A);
    }

    // Hàm cập nhật phần tử A[x][y] = val
    void updateY(int nodeX, int x_l, int x_r, int nodeY, int y_l, int y_r, int x, int y, long long val) {
        if (y_l == y_r) {
            if (x_l == x_r) {
                // NodeX_p và nodeY_p là lá, cập nhật
                seg[nodeX][nodeY] = val;
            } else {
                // Tại cùng nodeY (cột y), kết hợp 2 con X con
                seg[nodeX][nodeY] = seg[nodeX * 2][nodeY] + seg[nodeX * 2 + 1][nodeY];
            }
            return;
        }
        int midY = (y_l + y_r) / 2;
        if (y <= midY) {
            // Cập nhật vào con trái Y
            updateY(nodeX, x_l, x_r, nodeY * 2, y_l, midY, x, y, val);
        } else {
            // Cập nhật vào con phải Y
            updateY(nodeX, x_l, x_r, nodeY * 2 + 1, midY + 1, y_r, x, y, val);
        }
        // Sau khi cập nhật xong ở Y, kết hợp hai con Y để cập nhật nodeY
        seg[nodeX][nodeY] = seg[nodeX][nodeY * 2] + seg[nodeX][nodeY * 2 + 1];
    }

    // Hàm cập nhật cây X: duyệt theo trục X
    void updateX(int nodeX, int x_l, int x_r, int x, int y, long long val) {
        if (x_l != x_r) {
            int midX = (x_l + x_r) / 2;
            if (x <= midX) {
                updateX(nodeX * 2, x_l, midX, x, y, val);
            } else {
                updateX(nodeX * 2 + 1, midX + 1, x_r, x, y, val);
            }
        }
        // Sau khi cập nhật ở con X (hoặc nodeX chính là lá X), update cây Y
        updateY(nodeX, x_l, x_r, 1, 0, m - 1, x, y, val);
    }

    // Wrapper để người dùng gọi
    void update(int x, int y, long long val) {
        updateX(1, 0, n - 1, x, y, val);
    }

    // Hàm truy vấn theo Y tại một nodeX cố định: tính tổng cột y trong đoạn y ∈ [y1..y2],
    // nhưng nodeX đã được gọi sẵn cho đoạn hàng [x_l..x_r] “đang quan tâm”
    long long queryY(int nodeX, int nodeY, int y_l, int y_r, int y1, int y2) {
        // Nếu ngoài phần quan tâm
        if (y_r < y1 || y2 < y_l) {
            return 0LL;
        }
        // Nếu chứa hoàn toàn trong
        if (y1 <= y_l && y_r <= y2) {
            return seg[nodeX][nodeY];
        }
        int midY = (y_l + y_r) / 2;
        long long leftSum = queryY(nodeX, nodeY * 2, y_l, midY, y1, y2);
        long long rightSum = queryY(nodeX, nodeY * 2 + 1, midY + 1, y_r, y1, y2);
        return leftSum + rightSum;
    }

    // Hàm truy vấn cây X: tìm tổng trong hình chữ nhật [x1..x2] × [y1..y2]
    long long queryX(int nodeX, int x_l, int x_r, int x1, int x2, int y1, int y2) {
        // Nếu ngoài phần hàng quan tâm
        if (x_r < x1 || x2 < x_l) {
            return 0LL;
        }
        // Nếu đoạn hàng đang xét nằm hoàn toàn trong [x1..x2]
        if (x1 <= x_l && x_r <= x2) {
            // Chỉ cần query trên cây Y của nodeX
            return queryY(nodeX, 1, 0, m - 1, y1, y2);
        }
        int midX = (x_l + x_r) / 2;
        long long leftSum = queryX(nodeX * 2, x_l, midX, x1, x2, y1, y2);
        long long rightSum = queryX(nodeX * 2 + 1, midX + 1, x_r, x1, x2, y1, y2);
        return leftSum + rightSum;
    }

    // Wrapper để người dùng gọi
    long long query(int x1, int y1, int x2, int y2) {
        return queryX(1, 0, n - 1, x1, x2, y1, y2);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<long long>> A(N, vector<long long>(M, 0LL));

    // Nếu muốn khởi tạo ma trận từ input, có thể đọc A[i][j] ở đây

    // Tạo cây 2D
    SegmentTree2D st2d(N, M);
    st2d.build(A);

    // Xử lý Q thao tác:
    // Giả sử: kiểu 1 x y v = cập nhật A[x][y] = v
    //         kiểu 2 x1 y1 x2 y2 = truy vấn sum trong khung [x1..x2] × [y1..y2]
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, y;
            long long v;
            cin >> x >> y >> v;
            st2d.update(x, y, v);
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            long long ans = st2d.query(x1, y1, x2, y2);
            cout << ans << "n";
        }
    }

    return 0;
}

Giải thích chi tiết code segement tree 2D

Cấu trúc seg: Một vector hai chiều seg[nodeX][nodeY]. Về mặt vật lý, ta lưu seg là vector kích thước (4*n) × (4*m).

nodeX (từ 1 đến ~4*n) đại diện cho một đoạn hàng [x_l..x_r].
nodeY (từ 1 đến ~4*m) đại diện cho một đoạn cột [y_l..y_r].

Hàm buildX(nodeX, x_l, x_r, A):

Nếu x_l != x_r, chia đôi đoạn hàng, đệ quy xây cây cho con trái và con phải (mnemonics: nodeX*2 và nodeX*2+1).
Sau khi con đã được xây, ta gọi buildY để xây cây cột cho nodeX.

Hàm buildY(nodeX, x_l, x_r, nodeY, y_l, y_r, A):

Lúc này, nodeX đang “đại diện” cho đoạn hàng [x_l..x_r]. Mục tiêu: xây cây cột trên toàn bộ “vùng” [x_l..x_r] × [y_l..y_r].
Nếu y_l == y_r (tức là xét một cột cố định), thì:
- Nếu cũng là lá hàng (x_l == x_r), ta gán: seg[nodeX][nodeY] = A[x_l][y_l].
- Nếu không, ta đang ở cấp X không phải lá, nhưng cấp Y này đã là lá (chỉ một cột) → ta kết hợp giá trị của con trái và con phải trên Y:
```
seg[nodeX][nodeY] = seg[nodeX*2][nodeY] + seg[nodeX*2+1][nodeY];
```
Nếu y_l < y_r, ta chia đôi cột, đệ quy xuống cả con trái Y (nodeY*2) và con phải Y (nodeY*2+1), rồi gộp:
```
seg[nodeX][nodeY] = seg[nodeX][nodeY*2] + seg[nodeX][nodeY*2+1];
```

Hàm cập nhật updateX và updateY:

Cập nhật 2D về cơ bản là đi xuống cây X để tìm “điểm hàng” x. Khi đã tìm đúng nodeX cho x, ta tiếp tục gọi updateY(nodeX, x_l, x_r, 1, 0, m-1, x, y, val) để cập nhật trên cây Y:
- Ở updateY, nếu y_l == y_r == y (đang ở đúng cột) và x_l == x_r == x (đang ở đúng hàng), thì ta gán thẳng seg[nodeX][nodeY] = val.
- Nếu chỉ ở đúng cột nhưng đoạn hàng vẫn rộng (x_l != x_r), ta gộp giá trị của con trái và con phải X (tại cùng nodeY) để tính ra tổng cho hàng đó.
- Nếu cột vẫn phân mảnh, ta đệ quy xuống con trái/phải Y như 1D. Sau khi cập nhật xong Y ở nodeX, ta lại gộp hai con Y ở nodeX để cập nhật seg[nodeX][nodeY].

Hàm truy vấn queryX và queryY:

queryX(nodeX, x_l, x_r, x1, x2, y1, y2) tương tự 1D trên trục X:
- Nếu [x_l..x_r] ngoài [x1..x2], trả về 0.
- Nếu [x_l..x_r] nằm hoàn toàn trong [x1..x2], ta gọi queryY(nodeX, 1, 0, m-1, y1, y2) để lấy tổng toàn bộ cột y từ y1 đến y2 trong “vùng” hàng [x_l..x_r].
- Nếu phân mảnh, ta đệ quy xuống con trái và con phải X, rồi cộng kết quả.
queryY(nodeX, nodeY, y_l, y_r, y1, y2) tương tự 1D trên cột (giá trị tại nodeX cố định), nhưng thay vì lấy từ mảng gốc, ta lấy từ seg[nodeX][...].

Nhờ kiến trúc “cây X chứa hàng, mỗi node X lại có cây Y chứa cột”, ta chỉ cần O(log N) nhánh theo X, trong mỗi node X chỉ cần O(log M) nhánh theo Y → độ phức tạp mỗi truy vấn hoặc cập nhật là O(log N × log M).

Ví dụ minh hoạ

Ma trận A (giả sử N = 3, M = 3):

A = [ [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9] ]

Quá trình build:
1. buildX(1, 0, 2) phân nhánh: con trái [0..1], con phải [2..2].
2. Với mỗi nodeX, ta buildY để lưu tổng các cột:
  - Ví dụ nodeX=1 [0..2]: buildY(1,0,2,1,0,2) → nodeY=1 đại diện cột [0..2]. Nó lại phân nhánh Y: con trái cột [0..1], con phải [2..2].
    - Với [y=2]: tổng trên cột 2 từ hàng 0..2 = 3 + 6 + 9 = 18.
    - Với [y=0..1]: lại chia thành [0..0] (cột 0) và [1..1] (cột 1):
      - Cột 0, hàng 0..2: 1 + 4 + 7 = 12.
      - Cột 1, hàng 0..2: 2 + 5 + 8 = 15.
    - Cuối cùng, nodeY=1 lưu tổng toàn cột [0..2]: 12 + 15 + 18 = 45.
3. Tương tự, tạo cây cho nodeX=2 (hàng [0..1]) và nodeX=3 (hàng [2..2]), rồi tổng hợp lên nodeX=1.
Truy vấn ví dụ: tổng khung [x1..x2] = [0..1], [y1..y2] = [1..2].
1. queryX(1,0,2,0,1,1,2): vì [0..2] phân mảnh so với [0..1], ta tính cả hai con X:
  - Con trái X=2 ([0..1] nằm hoàn toàn trong [0..1]): gọi queryY(2,1,0,2,1,2) → tổng cột [1..2] trong hàng [0..1].
    - Cột 1: A[0][1] + A[1][1] = 2 + 5 = 7
    - Cột 2: A[0][2] + A[1][2] = 3 + 6 = 9
      → Kết quả con trái = 7 + 9 = 16.
  - Con phải X=3 ([2..2] ngoài [0..1]), trả về 0.
  - Tổng = 16 + 0 = 16.

Kết quả chính xác:

A[0][1] + A[0][2] + A[1][1] + A[1][2] = 2 + 3 + 5 + 6 = 16.

Kết luận

Ưu điểm
- Segment Tree 1D giúp ta thực hiện cập nhật (point update) và truy vấn (range query) trên mảng trong O(log N).
- Segment Tree 2D mở rộng cho ma trận, cho phép cập nhật một ô và truy vấn tổng (hoặc max/min…) trên khung con ma trận trong O(log N × log M).
Nhược điểm
- Bộ nhớ: Cần khoảng O(4N) cho 1D, và khoảng O(4N × 4*M) cho 2D. Nếu N và M ~ 105, cây 2D sẽ quá lớn (không khả thi). Thông thường 2D segment tree chỉ dùng khi N, M ≤ vài nghìn.
- Triển khai phức tạp: 2D phức tạp gấp nhiều lần so với 1D. Cần chú ý rất cẩn thận trong việc chia nhánh, gộp kết quả, để tránh lỗi index ngoài vùng bộ nhớ.
Một số biến thể
- Thay vì tìm tổng lớn nhất ta sẽ tìm số lớn nhất trong khoảng truy vấn bằng cách dùng segement tree.
- Với nhu cầu “cập nhật cả đoạn (range update) và truy vấn đoạn (range query)”, ta cần thêm Kỹ thuật Lazy Propagation để đẩy nháp (lazy) xuống cây, giữ thời gian O(log N) cho 1D. Tương tự, có thể áp dụng lazy 2D nhưng rất phức tạp.
- Nếu chỉ quan tâm “truy vấn đáy” (point query) và “cập nhật đoạn” (range update), có thể dùng Fenwick Tree (Binary Indexed Tree) 1D (O(log N)) hoặc Fenwick Tree 2D (O(log N × log M)). Fenwick Tree đơn giản hơn mã nguồn nhưng chỉ hỗ trợ một số loại tính toán nhất định (ví dụ tổng).

Các bài luyện tập thêm về segment tree

Các bài đọc thêm

https://codedream.edu.vn/cay-ao-phan-1-1/

Segment Tree 1D (Cây Đoạn Thẳng 1 Chiều)

Khái niệm và động lực sử dụng

Cách thiết kế segment tree

Cài đặt segment tree 1D bằng C++
Dưới đây minh hoạ một segment tree hỗ trợ:

Segment Tree 2D (Cây Đoạn Thẳng 2 Chiều)

Khái niệm về segment tree 2D

Ý tưởng thiết kế segment tree 2D

Kết luận

Các bài luyện tập thêm về segment tree

Các bài đọc thêm

Bài viết liên quan:

Bài viết cùng chủ đề:

Cây khung nhỏ nhất: Kruskal, Prim

Nhân ma trận – Quy hoạch động nhân ma trận

Quy hoạch động bitmask Phần 1/2

Các công thức toán học trong lập trình

DP Digit – Quy hoạch động chữ số

Thuật toán LCA (Lowest Common Ancestor): Lý thuyết và cài đặt trong C++

Code Dream Team

Để lại một bình luận Hủy

Liên hệ

Segment Tree 1D (Cây Đoạn Thẳng 1 Chiều)

Khái niệm và động lực sử dụng

Cách thiết kế segment tree

Cài đặt segment tree 1D bằng C++ Dưới đây minh hoạ một segment tree hỗ trợ:

Segment Tree 2D (Cây Đoạn Thẳng 2 Chiều)

Khái niệm về segment tree 2D

Ý tưởng thiết kế segment tree 2D

Kết luận

Các bài luyện tập thêm về segment tree

Các bài đọc thêm

Bài viết liên quan:

Bài viết cùng chủ đề:

Cây khung nhỏ nhất: Kruskal, Prim

Nhân ma trận – Quy hoạch động nhân ma trận

Quy hoạch động bitmask Phần 1/2

Các công thức toán học trong lập trình

DP Digit – Quy hoạch động chữ số

Thuật toán LCA (Lowest Common Ancestor): Lý thuyết và cài đặt trong C++

Code Dream Team

Để lại một bình luận Hủy

Cài đặt segment tree 1D bằng C++
Dưới đây minh hoạ một segment tree hỗ trợ: