树状数组

1. 二进制数最右边的一个1，连带着它之后的0
2. 维护 区间

• 单点修改

void update(int i, int val) {
	for (; i < tree.size(); i += i & -i) {
		tree[i] += val;
	}
}
Copy

• 求前n项和

// 返回下标在 [1,i] 的元素之和,
int pre(int i) {
	int res = 0;
	while (i > 0) {
		res += tree[i];
		i &= i - 1;
	}
	return res;
}
Copy

• 区间求和

// 返回下标在 [l,r] 的元素之和
int query(int l, int r) {
	if (r < l) {
		return -1;
	}
	return pre(r) - pre(l - 1);
}
Copy

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);
	}

};
Copy

3072. 将元素分配到两个数组中 II