// Implementation of different types of fenwick


// 1.) Point update, range query

#define ll long long
void update(ll x, ll nv) { // add nv to index x. (nv can be both positive or negative)
    for(; x<=n; x+=x&(-x))fw[x] += nv;
    return;
}
ll sum(ll x) { // returns sum of numbers from 1 to n
    ll res = 0;
    for(; x; x-=x&(-x))res += fw[x];
    return res;
}
ll range_sum(ll a,ll b) { // returns sum of numbers from a to b
    return sum(b)-sum(a-1);
}



2.) Range update, point query
(works like a static sum(but dynamic this time). Note that sum(x) returns only the value of index x and not the sum of 1 to x)

#define ll long long
void update(ll x, ll y, ll v) { // adds v to numbers of index x to y. (v can be positive or negative)
    for(; x<=n; x+=x&(-x)) fw[x] += v;
    ++y;
    for(; y<=n; y+=y&(-y)) fw[y] -= v;
}
ll sum(ll x) { /*point query btw, returns value at index x*/
    ll res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}


3.) Range update, range query

#define ll long long
void update(ll x, ll y, ll v) { //adds v to numbers of index x to y. (v can be positive or negative)
    for (ll tx=x; tx <= n; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (ll ty=y+1; ty <= n; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
ll sum (ll x) { // returns sum of numbers of index 1 to n
    ll res = 0;
    for (ll tx=x; tx; tx -= tx&(-tx)) {
      res += fw[tx]*x + fw2[tx];
    }
    return res;
}
ll range_sum(ll x, ll y) { // returns sum of numbers of index x to y
    return sum(y)-sum(x-1);
}