Ленивое ДО

vector<int> v(4 * n, 0);

vector<int> up(4 * n, 0);

int func(int l, int r)
{
    return l + r;
}

void push_far(int p, int lf, int rf)
{
    if (lf != rf)
    {
        int m = (rf + lf) / 2;
        v[p * 2] += up[p] * (m - lf + 1);
        up[p * 2] += up[p];
        v[p * 2 + 1] = up[p] * (rf - m);
        up[p * 2 + 1] += up[p];
    }
    up[p] = 0;
}

void setDO(int i, int num, int p = 1, int lf = 0, int rf = n - 1)
{
    if (rf == lf)
    {
        v[p] = num;
        return;
    }

    if (up[p])
        push_far(p, lf, rf);

    int m = (rf + lf) / 2;
    if (i <= m)
        setDO(i, num, p * 2, lf, m);
    else
        setDO(i, num, p * 2 + 1, m + 1, rf);
    v[p] = func(v[p * 2], v[p * 2 + 1]);
}

int getDO(int l, int r, int p = 1, int lf = 0, int rf = n - 1)
{
    if (l == lf && r == rf)
        return v[p];

    if (up[p])
        push_far(p, lf, rf);

    int m = (rf + lf) / 2;
    if (rf <= m)
        return getDO(l, r, p * 2, lf, m);
    if (lf > m)
        return getDO(l, r, p * 2 + 1, m + 1, rf);
    return func(getDO(l, m, p * 2, lf, m), getDO(m + 1, r, p * 2 + 1, m + 1, rf));
}

void setPerDO(int l, int r, int inc, int p = 1, int lf = 0, int rf = n - 1)
{
    if (l == lf && r == rf)
    {
        v[p] += inc * (r - l + 1);
        up[p] += inc;
        return;
    }

    if (up[p])
        push_far(p, lf, rf);

    int m = (rf + lf) / 2;
    if (rf <= m)
    {
        setPerDO(l, r, inc, p * 2, lf, m);
    }
    else if (lf > m)
    {
        setPerDO(l, r, inc, p * 2 + 1, m + 1, rf);
    }
    else
    {
        setPerDO(l, m, inc, p * 2, lf, m);
        setPerDO(m + 1, r, inc, p * 2 + 1, m + 1, rf);
    }
    v[p] = func(v[p * 2], v[p * 2 + 1]);
}