Pull to refresh

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

Reading time 5 min
Views 40K
Я расскажу о структуре под названием дерево отрезков и приведу его простую реализацию на языке С++. Эта структура весьма полезна в случаях, когда необходимо часто искать значение какой-то функции на отрезках линейного массива и иметь возможность быстро изменять значения группы подряд идущих элементов.
Типичный пример задачи на дерево отрезков:
Есть линейный массив, изначально заполненный некоторыми данными. Далее приходят 2 типа запросов:
1й тип — найти значение максимального элемента на отрезке массива [a..b].
2й тип — заменить iй элемент массива на x.
Возможен запрос «добавить х ко всем элементам на отрезке [a..b]», но в данной статье я его не рассматриваю.
С помощью дерева отрезков можно искать не только максимум чисел, но и любую функцию, удовлетворяющую свойству ассоциативности.
image
Это ограничение связано с тем, что используется предпросчет значений для некоторых отрезков.

Так же можно искать, например, не значения, а порядковые номера элементов.
Желательно, что бы функция имела «нейтральный» аргумент, который не оказывает влияния на результат. Например, для суммы это число 0: (a + 0 = a), а для максимума это бесконечность: max(a, -inf) = a.
Итак, поехали.
Самый простой (и медленный) способ решать представленную выше задачу, это завести линейный массив, и покорно делать то, что от нас хотят.
при такой реализации время нахождения ответа на запрос имеет порядок О(n). в среднем, придется пройтись по половине массива что бы найти максимум. Хотя есть и положительные моменты — изменение значения какого-либо элемента требует O(1) времени. Этот алгоритм можно ускорить в 2 раза, если выполнить небольшой предпросчет: для каждой пары элементов найдем значение максимального из них, и запишем в другой массив. Тогда при поиске максимума на отрезке, для каждой пары элементов уже известно значение большего, и сравнивать придется только с ним. остается только аккуратно проверить граничные элементы, так как граница запрашиваемого отрезка не обязательно четная.
На рисунке выделены элементы, которые необходимо проверять.

image

Понятно, что над этими массивами можно ввести еще один, что бы поиск был еще в 2 раза быстрее, а над ним еще один… и так до тех пор, пока самый верхний массив не будет состоять из одного элемента. Как не трудно догадаться, значение единственного элемента в самом верхнем массиве – это значение максимального элемента.

image

Некоторые пояснения: число рядом с вершиной дерева — это положение этой вершины в реальном массиве. При такой реализации хранения дерева очень удобно искать предка и потомков вершины: предок вершины i имеет номер i/2, а потомки номера i*2 и i*2+1. Из рисунка видно, что необходимо, что бы длинна массива была степенью двойки. Если это не так, то массив можно в конце дополнить нейтральными элементами. Расход памяти на хранение структуры от 2n до 4n, (n — количество элементов).
Алгоритм поиска «сверху» (есть еще и «снизу») весьма прост и в понимании и в реализации (хотя тех, кто не знаком с рекурсией, это всё может озадачить).
Алгоритм таков:
Начинаем опрос с вершины 1 (самая верхняя).
1.пусть текущая вершина знает максимум на промежутке l..r.
«пересекаются области [a..b] и [l..r] ?»
возможные варианты:
a. вообще не пересекаются.
что бы не влиять на результат вычисления, вернем нейтральный элемент (-бесконечность).
b. область [l..r] полностью лежит внутри [a..b].
вернуть предпросчитанное значение в текущей вершине.
с. другой вариант перекрытия областей.
спросить то же самое у детей текущей вершины и вычислить максимум среди них (смотрите код, если непонятно).

Как видно, алгоритм короткий, но рекурсивный. Временная сложность O(logN), что намного луче, чем О(N). например, при массиве длинной 10^9 элементов, необходимо примерно 32 сравнения.
Изменить число в этой структуре еще проще — надо пройти по всем вершинам от заданной до 1й, и если значение в текущей меньше чем новое, то заменить его. Это так же занимает O(log N) времени.
Реализация алгоритма.
Предполагается, что количество элементов массива не более 1024 (номера 0..1023).
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5. #define INF 1000000000 // предпологаем, что чисел больше такого не будет.
  6.  
  7. #define TREE_REAL_DATA 1024     // максимальное допустимое количество элементов
  8. int tree_data[TREE_REAL_DATA * 2];  
  9.  
  10. // основная функция поиска.
  11. // аргументы: p - текушая вершина(пронумерованы согласно рисунку).
  12. // l, p - левая и правая границы отрезка, для которого tree_data[p] является максимумом.
  13. // вообще можно было обойтись без этих параметров, и определять их исходя из p, но так проще и понятней.
  14. // a, b - левая и правая границы отрезка, для которого необходимо найти минимум.
  15. int __tree_find_max(int p, int l, int r, int a, int b) 
  16. {
  17. if (< l || r < a) return -INF;
  18. if (<= l && r <= b) return tree_data[p];
  19. int r1 = __tree_find_max(p*2  , l, (l+r) / 2,   a, b); // опрос левого предка
  20. int r2 = __tree_find_max(p*2+1(l+r)/2 + 1, r, a, b); // опрос правого предка
  21. return max(r1, r2); // нахождение большего из левого и правого поддеревьев
  22. }
  23.  
  24. // более юзабильная оболочка для функции выше.
  25. int tree_find_max(int a, int b)
  26. {
  27. return __tree_find_max(10, TREE_REAL_DATA - 1, a, b);
  28. }
  29.  
  30. // обновление элемента № р.
  31. void tree_update(int p, int x) 
  32. {
  33. += TREE_REAL_DATA; // преобразование позиции p к позиции в самом нижнем массве,
  34. // в котором реально находится массив со значениями.
  35. tree_data[p] = x;
  36. for(p/=2; p ; p/=2) {
  37. if (tree_data[* 2] > tree_data[* 2 + 1])
  38. tree_data[p] = tree_data[* 2];
  39. else tree_data[p] = tree_data[* 2 + 1];
  40. }
  41. } 
  42.  
  43. // простейшая инициализация - установка всех значений в -INF
  44. void tree_init()
  45. {
  46. for (int i = 0; i < TREE_REAL_DATA * 2; i++) 
  47. tree_data[i] = -INF;
  48. }
  49.  
  50. int main()
  51. {
  52. tree_init();
  53. while ( 1 ){
  54. char c;
  55. scanf("%c"&c);
  56. if (== 'Q') return 0; // выход
  57. if (== 'F') {  // найти максимум на интервале a..b
  58. int a, b;
  59. scanf("%d%d"&a, &b);
  60. printf("%d\n", tree_find_max(a, b));
  61. }
  62. if (== 'U') { // установить значение элемента p равым x.
  63. int p, x; 
  64. scanf("%d%d"&p, &x);
  65. tree_update(p, x);
  66. }
  67. }
  68. }
  69.  
  70.  



Вот, в общем, и все, что необходимо в первую очередь знать о дереве отрезков.
Для разнообразия можно еще разобраться с алгоритмом вычисления «снизу» (он, кстати, нерекурсивный), хотя я нахожу его менее симпатичным. Ну и, конечно же, стоит разобраться с быстрым добавлением суммы ко всем элементам на отрезке (тоже за O(log N)), но это будет слишком утомительно для человека, который впервые разбирается с деревом отрезков.
Tags:
Hubs:
+5
Comments 6
Comments Comments 6

Articles