Fenwick Tree (BIT)

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