Двухменый segment_tree

void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
    if (ly == ry) {
    
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
        return;

    }
    else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
    }
    t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}

void Test()
{
    N = 20;
    M = 20;

    memset(t, 0, sizeof(t));

    vector<vector<int> > c(N, vector<int>(M, 0));

    for (int nTest = 1; nTest <= 20000; nTest++)
    {
        int x = rand() % M;
        int y = rand() % N;
        int val = rand() % 1000;

        update_x(1, 0, M - 1, x, y, val);
        c[y][x] = val;

        int tx = rand() % M;
        int lx = rand() % (tx + 1);

        int ty = rand() % N;
        int ly = rand() % (tx + 1);

        val = 0;
        for (int x = lx; x <= tx; x++)
        {
            for (int y = ly; y <= ty; y++)
                val  += c[y][x];
        }

        int val2 = sum_x(1, 0, M - 1, lx, tx, ly, ty);
        assert (val == val2);

    }
}