Фенвик

vector<int> fenv(n, 0);

int getSum(int r)
{
    int sum = 0;
    while (r >= 0)
    {
        sum += fenv[r];
        r = r & (r + 1) - 1;
    }
    return sum;
}

int getSum(int l, int r)
{
    return getSum(r) - getSum(l - 1);
}

int inc(int i, int a)
{
    while (i < n)
    {
        fenv[i] += a;
        i = i | (i + 1);
    }
}

void setFenv(vector<int>& orig)
{
    fenv.clear();
    fenv.resize(orig.size(), 0);
    for (int i = 0; i < orig.size(); i++)
        inc(i, orig[i]);
}