Дерево отрезков: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 120: Строка 120:
* [http://codeforces.ru/gym/100094/problem/B Codeforces #100094.B — Грибы]
* [http://codeforces.ru/gym/100094/problem/B Codeforces #100094.B — Грибы]
* [http://codeforces.ru/gym/100094/problem/C Codeforces #100094.C — Художник] (aka [http://codeforces.ru/gym/100255/problem/C Codeforces #100255.C — Художник])
* [http://codeforces.ru/gym/100094/problem/C Codeforces #100094.C — Художник] (aka [http://codeforces.ru/gym/100255/problem/C Codeforces #100255.C — Художник])
* [http://codeforces.ru/gym/100255/problem/B Codeforces #100255.B — Большая стена]


== Ссылки ==
== Ссылки ==

Версия от 18:37, 26 октября 2014

Запрос на отрезке и модификация отдельных элементов

  • Если отрезок текущей вершины не пересекается с отрезком запроса, то возвращается нейтральное значение.
  • Если отрезок текущей вершины целиком включён в отрезок запроса, то возвращается значение, хранящееся в текущей вершине.
  • Во всех остальных случаях запрос перенаправляется потомкам текущей вершины.

Можно выделить два распространённых способа реализации данной логики:

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];
}

Ссылки на задачи

Ссылки