date: 2024-06-21
title: Fenwick
status: UNFINISHED
dg-publish: false
author:
- AllenYGY
tags:
- NOTE
- DataStructure
- Fenwick
created: 2024-06-21T18:07
updated: 2024-06-22T16:18Fenwick|树状数组
最简单的树状数组支持两种操作，时间复杂度均为
巧妙地利用了二进制（实际上，树状数组的英文名BIT，直译过来就是二进制下标树）
void update(int i, int val) {
for (; i < tree.size(); i += i & -i) {
tree[i] += val;
}
}
// 返回下标在 [1,i] 的元素之和,
int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
// 返回下标在 [l,r] 的元素之和
int query(int l, int r) {
if (r < l) {
return -1;
}
return pre(r) - pre(l - 1);
}
class Fenwick {
vector<int> tree;
public:
Fenwick(int n) : tree(n) {}
// 把下标为 i 的元素增加 1
void add(int i) {
while (i < tree.size()) {
tree[i]++;
i += i & -i; // i & -i 会得到 i 的最后一个 1 即 lowbit
}
}
void update(int i, int val) {
for (; i < tree.size(); i += i & -i) {
tree[i] += val;
}
}
// 返回下标在 [1,i] 的元素之和
int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
// 返回下标在 [l,r] 的元素之和
int query(int l, int r) {
if (r < l) {
return -1;
}
return pre(r) - pre(l - 1);
}
};