Дерево отрезков
Перейти к навигации
Перейти к поиску
Запрос на отрезке и модификация отдельных элементов
- Если отрезок текущей вершины не пересекается с отрезком запроса, то возвращается нейтральное значение.
- Если отрезок текущей вершины целиком включён в отрезок запроса, то возвращается значение, хранящееся в текущей вершине.
- Во всех остальных случаях запрос перенаправляется потомкам текущей вершины.
Можно выделить два распространённых способа реализации данной логики:
if (r < vl || vr < l)
//отрезки не пересекаются
if (l <= vl && vr <= r)
//отрезок текущей вершины принадлежит отрезку запроса
query(2 * v + 1, vl, vm, l, r);
query(2 * v + 2, vm + 1, vr, l, r);
|
if (l > r)
//отрезки не пересекаются
if (l == vl && vr == r)
//отрезок текущей вершины принадлежит отрезку запроса
query(2 * v + 1, vl, vm, l, min(r, vm));
query(2 * v + 2, vm + 1, vr, max(l, vm + 1), r);
|
int t[4 * 100010];
void build(int v, int vl, int vr, int a[]) {
if (vl == vr) {
t[v] = a[vl];
return;
}
int vm = vl + (vr - vl) / 2;
build(2 * v + 1, vl, vm, a);
build(2 * v + 2, vm + 1, vr, a);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
int query(int v, int vl, int vr, int l, int r) {
if (r < vl || vr < l)
return 0;
if (l <= vl && vr <= r)
return t[v];
int vm = vl + (vr - vl) / 2;
int ql = query(2 * v + 1, vl, vm, l, r);
int qr = query(2 * v + 2, vm + 1, vr, l, r);
return ql + qr;
}
void modify(int v, int vl, int vr, int pos, int val) {
if (pos < vl || vr < pos)
return;
if (pos == vl && vl == vr) {
t[v] += val;
return;
}
int vm = vl + (vr - vl) / 2;
modify(2 * v + 1, vl, vm, pos, val);
modify(2 * v + 2, vm + 1, vr, pos, val);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
Запрос на отрезке и модификация на отрезке
- Считаем, что актуальное значение в вершине v равно t[v] + add[v] * (vr - vl + 1).
- Перед выводом результата или передачей запроса будем спускать значение add[v] потомкам текущей вершины при помощи функции push().
int t[4 * 100010], add[4 * 100010];
void push(int v, int vl, int vr) {
if (vl != vr) {
add[2 * v + 1] += add[v];
add[2 * v + 2] += add[v];
}
t[v] += add[v] * (vr - vl + 1);
add[v] = 0;
}
void build(int v, int vl, int vr, int a[]) {
if (vl == vr) {
t[v] = a[vl];
return;
}
int vm = vl + (vr - vl) / 2;
build(2 * v + 1, vl, vm, a);
build(2 * v + 2, vm + 1, vr, a);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
int query(int v, int vl, int vr, int l, int r) {
push(v, vl, vr);
if (r < vl || vr < l)
return 0;
if (l <= vl && vr <= vr)
return t[v];
int vm = vl + (vr - vl) / 2;
int ql = query(2 * v + 1, vl, vm, l, r);
int qr = query(2 * v + 2, vm + 1, vr, l, r);
return ql + qr;
}
void modify(int v, int vl, int vr, int l, int r, int val) {
push(v, vl, vr);
if (r < vl || vr < l)
return;
if (l <= vl && vr <= vr) {
add[v] += val;
push(v, vl, vr);
return;
}
int vm = vl + (vr - vl) / 2;
modify(2 * v + 1, vl, vm, l, r, val);
modify(2 * v + 2, vm + 1, vr, l, r, val);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
Ссылки на задачи
- Codeforces #100094.A — Это как пятый, но на один пониже (aka Codeforces #100249.D — Экзамен)
- Codeforces #100094.B — Грибы
- Codeforces #100094.C — Художник (aka Codeforces #100255.C — Художник)
- Codeforces #100255.B — Большая стена