Дерево отрезков

Достаточно полезная тема не только в олимпиадном программировании. Если Вы уже осилили двоичные кучи (binary heap), то Вас порадует повторное использование трюка для простого хранения дерева в массиве.
Практически все задачи на дерево отрезков сводятся к необходимости быстрого вычисления некоторой ассоциативной операции для всевозможных диапазонов изменения индексов массива (отрезков массива). Часто к этому требованию добавляется необходимость менять значения элементов массива или их значений на некотором отрезке. Сутью подхода является предварительное построение за [latex]O \left( n \right)[/latex] некоторого дерева, вершины которого хранят значения операции для определенных отрезков массива. Далее используются определенные приёмы нахождения за [latex]O \left( \log n \right)[/latex] значений для тех отрезков, которые не были вычислены предварительно. Пересчет значений узлов при модификации также осуществляется за [latex]O \left( \log n \right)[/latex].
Алгоритм может быть модифицирован для многомерных массивов и более сложных последовательных структур.

Что почитать?

• На e-maxx
• Задачи с разбором и кодом на codeforces
• Просто о моноидах

Что порешать?

• На e-olymp
  1. Задачи с единичной модификацией
  2. Задачи с множественной модификацией
  3. Разрозненные задачи
• На timus
  1. 1028. Stars
  2. 1090. In the Army Now
  3. 1439. Battle with You-Know-Who
  4. 1470. UFOs
  5. 1471. Distance in the Tree
  6. 1521. War Games 2
  7. 1523. K-inversions
  8. 1542. Autocompletion
  9. 1717. Eligibility Rules
  10. 1846. GCD 2010
• На codeforces
• На Sphere Online Judge
  1. COT — Count on a tree
  2. GOT — Gao on a tree
  3. DQUERY — D-query
  4. GSS1 — Can you answer these queries I
  5. GSS2 — Can you answer these queries II
  6. MKTHNUM — K-th Number
  7. PT07J — Query on a tree III

Related Images: