Fenwick Tree (BIT) - YessineJallouli/Competitive-Programming GitHub Wiki
Sum of a range + update
#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;
const int N = 1e5 + 7;
int tree[N], a[N];
int n;
// Fenwick tree is used only for sum and xor (I guess)
void upd(int x, int val) {
for (; x <= n; x += x&(-x))
tree[x]+= val;
}
int get(int x) {
int res = 0;
for (; x; x-= x&(-x))
res+= tree[x];
return res;
}
int main() {
SaveTime
cin >> n;
}
Sum + Update in a matrix
void upd(int x, int y, int val) {
for (; x <= n; x += x&(-x))
for (int j = y; j <= n; j+= j&(-j))
tree[x][j]+= val;
}
ll get(int x, int y) {
ll res = 0;
for (; x; x-= x&(-x))
for (int j = y; j ; j-=j&(-j))
res+= tree[x][j];
return res;
}