Truy vấn tổng khoảng và cập nhật căn bậc hai bằng C++ (Binary Indexed Tree)

Cho mảng, 2 loại truy vấn: update(L,R) — thay mỗi phần tử trong [L,R] bằng căn bậc 2 nguyên của nó; query(L,R) — tính tổng [L,R]. Mảng 1-based.

Cách đơn giản O(Q×N)

Duyệt mảng mỗi truy vấn.

Cách hiệu quả: Binary Indexed Tree (Fenwick Tree) + Set

• BIT hỗ trợ update_point và prefix_sum O(log N).
• Chỉ cập nhật phần tử > 1 (vì căn bậc 2 của 1 vẫn là 1). Dùng set lưu chỉ số các phần tử > 1.
• Khi update [L,R]: dùng lower_bound tìm chỉ số ≥ L trong set, lặp cập nhật BIT và mảng, nếu phần tử trở thành 1 → xóa khỏi set.
• Query tổng: sum(R) - sum(L-1).

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
int BIT[MAXN + 1];

void updateBIT(int idx, int delta, int n) {
    while (idx <= n) { BIT[idx] += delta; idx += idx & -idx; }
}
int queryBIT(int idx) {
    int s = 0;
    while (idx > 0) { s += BIT[idx]; idx -= idx & -idx; }
    return s;
}

int main() {
    int nums[] = {0, 9, 4, 1, 5, 2, 3};
    int n = sizeof(nums)/sizeof(nums[0]) - 1;
    int q[4][3] = {{1,1,3},{2,1,2},{1,2,5},{1,4,5}};
    set s;
    for (int i = 1; i <= n; i++) {
        if (nums[i] > 1) s.insert(i);
        updateBIT(i, nums[i], n);
    }
    for (int i = 0; i < 4; i++) {
        if (q[i][0] == 2) { // update
            while (true) {
                auto it = s.lower_bound(q[i][1]);
                if (it == s.end() || *it > q[i][2]) break;
                int idx = *it;
                int newVal = (int)sqrt(nums[idx]);
                updateBIT(idx, newVal - nums[idx], n);
                nums[idx] = newVal;
                if (newVal == 1) s.erase(it);
                q[i][1] = idx + 1;
            }
        } else { // query
            cout << "query" << i+1 << ": " << queryBIT(q[i][2]) - queryBIT(q[i][1]-1) << endl;
        }
    }
    return 0;
}

Kết quả

query1: 14 query3: 10 query4: 7

Kết luận

Range sum query + range sqrt update dùng BIT + set chỉ số > 1. Code C++.