Cập nhật chỉ số và truy vấn GCD trên đoạn dùng Segment Tree trong C++

Hỗ trợ 2 thao tác trên mảng: (1) cập nhật giá trị tại chỉ số, (2) truy vấn GCD trên đoạn [L, R]. Dùng Segment Tree.

Cấu trúc Segment Tree cho GCD

• Node lưu GCD của đoạn.
• Merge: gcd(left, right).
• Cập nhật: lan truyền diff lên cha.

Triển khai C++

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

int mid(int l, int r) { return l + (r-l)/2; }

void build(int* st, int arr[], int node, int l, int r) {
    if (l == r) { st[node] = arr[l]; return; }
    int m = mid(l, r);
    build(st, arr, 2*node+1, l, m);
    build(st, arr, 2*node+2, m+1, r);
    st[node] = std::gcd(st[2*node+1], st[2*node+2]);
}

void update(int* st, int node, int l, int r, int idx, int val) {
    if (l == r) { st[node] = val; return; }
    int m = mid(l, r);
    if (idx <= m) update(st, 2*node+1, l, m, idx, val);
    else update(st, 2*node+2, m+1, r, idx, val);
    st[node] = std::gcd(st[2*node+1], st[2*node+2]);
}

int queryGCD(int* st, int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return st[node];
    if (r < ql || l > qr) return 0;
    int m = mid(l, r);
    return std::gcd(queryGCD(st, 2*node+1, l, m, ql, qr),
                    queryGCD(st, 2*node+2, m+1, r, ql, qr));
}

int main() {
    int arr[] = {2, 5, 16, 7, 9, 23};
    int n = 6;
    int size = 4*n; // đủ lớn
    int* st = new int[size];
    build(st, arr, 0, 0, n-1);
    
    cout << queryGCD(st, 0, 0, n-1, 2, 5) << endl; // GCD(16,7,9,23) = 1
    
    update(st, 0, 0, n-1, 2, 14); // arr[2] = 14
    cout << queryGCD(st, 0, 0, n-1, 2, 5) << endl; // GCD(14,7,9,23) = 1
    return 0;
}

Kết quả

1
1

Độ phức tạp: O(log n) cho cả update và query.