Fenwick Tree

void upd (int i, int val) {
    for (; i <= n; i += (i & -i))
        pre[i] += val;
    return;
}

int get (int i) {
    int res = 0;
    for (; i > 0; i -= i & (-i))
        res += pre[i];
    return res;
}