树状数组的一个优雅实现（C++）

发表于 更新于 分类于 ， 阅读次数：

废话不多说，直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class BIT {
private:
    vector<int> tree;
    int n;
public:
    BIT(int _n) : n(_n), tree(_n + 1) {}

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

    // 查询前缀和
    int query(int x) {
        int ret = 0;
        while (x) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    // 更新
    void update(int x, int v) {
        while (x <= n) {
            tree[x] = v;
            x += lowbit(x);
        }
    }
};

从leetcode的一个题解里面抄的，构造函数接受一个参数_n表示数组长度，并初始化（为0），做了一些改动，感觉非常舒适。

TODO

  • 从数组或者迭代器中初始化
  • 使用模板，不局限于int类型