content/datastructures/fenwickTree.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<ll> tree;

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

void init(int n) {
	tree.assign(n + 1, 0);
}

ll prefix_sum(int i) {
	ll sum = 0;
	for (i++; i > 0; i -= i & -i) sum += tree[i];
	return sum;
}