Задача №2.2

//проталкивание вниз
void push_down_1(int x, vector<int>& dop)
{
    if (2 * x + 1 < dop.size())
    {
        dop[2 * x + 1] = dop[x];
        push_down_1(2 * x + 1, dop);

        dop[2 * x + 2] = dop[x];
        push_down_1(2 * x + 2, dop);

        dop[x] = 0;
    }
}
// увеличение отрезка на х
void dop_plant(int start,const int& x,const int& left,const int& right,int lx,int rx, vector<int>& dop)
{
        if (left >= rx or lx >= right)
            return;
        if (lx == left and rx == right)
        {
            dop[start] += x;
            return;
        }
        int m = (lx + rx) / 2;
        dop_plant(start * 2 + 1, x, left, right, lx, m, dop);
        dop_plant(start * 2 + 2, x, left, right, m, rx, dop);
}

//строительство дерева с учтенным увеличением
vector<int> end_tree(vector<int>& array, vector<int>& dop, int lenght)
{
    for (int i = 0; i < dop.size(); i++)
    {
        if (dop[i] != 0)
        {
            push_down_1(i, dop);
            break;
        }
    }
    if (lenght % 2 == 0)
    {
        vector<int> output(lenght * 2 - 1);
        for (int i = 0; i < lenght; i++)
        {
            output[lenght - 1 + i] = array[i]+dop[lenght-1+i];
        }
        for (int i = lenght - 2; i >= 0; i--)
        {
            output[i] = output[i * 2 + 1] + output[i * 2 + 2];
        }
        return output;
    }
    else
    {
        vector<int> output((lenght + 1) * 2 - 1);
        for (int i = 0; i < lenght; i++)
        {
            output[lenght + i] = array[i] + dop[lenght - 1 + i];
        }
        for (int i = lenght - 1; i >= 0; i--)
        {
            output[i] = output[i * 2 + 1] + output[i * 2 + 2];
        }
        return output;
    }
}
// сумма на отрезке(передается дерево после end_tree)
int sum(int l, int r, int x, int lx, int rx,const vector<int>& array)
{
    if (l >= rx or lx >= r)
        return 0;
    if (lx >= l and rx <= r)
        return array[x];
    int m = (lx + rx) / 2;
    int sl = sum(l, r, 2 * x + 1, lx, m, array);
    int sr = sum(l, r, 2 * x + 2, m, rx, array);
    return sl + sr;
}