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 < ssize(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 > 0; i &= i-1) sum += tree[i];
	return sum;
}