树状数组的一个优雅实现(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类型