C++ 树状数组模版

• 树状数组是一种高效的数据结构，适用于处理区间更新和查询问题。

• 树状数组模板

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
    int n;

    int lowbit(int x) {
        return x & (-x);
    }

public:
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    void update(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += lowbit(idx);
        }
    }

    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    int range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    FenwickTree ft(10); // 初始化大小为10的树状数组
    ft.update(3, 5); // 更新索引3的值为5
    cout << "Sum from index 1 to 5: " << ft.range_query(1, 5) << endl; // 查询区间和
    return 0;
}

• 要点总结：树状数组通过lowbit运算简化区间查询和更新操作，提高效率。12345678