Тема: Двухменый segment_tree
Есть подозрение что на странице http://e-maxx.ru/algo/segment_tree в update_y пропущен
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]);
для случай ly != ry
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Feedback » Двухменый segment_tree
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Есть подозрение что на странице http://e-maxx.ru/algo/segment_tree в update_y пропущен
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]);
для случай ly != ry
Не. Тоже так нельзя
Вот такой прходит:
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);
}
}
Понял, туплю.
Спасибо, что протестил - я как-то эту статью с деревьями отрезков поленился всю тестировать
Ну почему же через 1 путь? В dfs'е все так же пропускается блокирующий поток (не только 1 путь). Посмотри внимательнее - в dfs return flow только если уже нечево пропускать с текущей вершины (в rest поддерживается количество потока, которое еще можно пропустить на следующий уровень). И так же отсекаются "тупики" (через ptr).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Feedback » Двухменый segment_tree