Перейти к содержимому


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


В этой теме нет ответов

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 41 сообщений
  • ГородВитебск

Отправлено 14 ноября 2012 - 12:45

Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. скорость алгоритма (O(log n)) реализовать операции следующего вида:
  • Нахождение суммы на отрезке [L;R]
  • Нахождение минимума и максимума на отрезке [L;R]
  • Изменение элементов (увеличение и уменьшение) на отрезке [L;R]
Вообще, дерево отрезков — очень гибкая структура, и число задач, решаемых ей, теоретически неограниченно. Помимо приведённых выше видов операций с деревьями отрезков, также возможны и гораздо более сложные операции. Но об этом позже.



Важной особенностью деревьев отрезков является то, что они потребляют линейный объём памяти: стандартному дереву отрезков требуется порядка 4n элементов памяти для работы над массивом размера n.

Например в задаче n<=100000. Значит нам надо сделать массив [0..400000].

Структура дерева

Подсчитаем и запомним сумму элементов всего массива, т.е. отрезка a[0..n-1] Также посчитаем сумму на двух половинках этого массива: a[0..n/2] и a[n/2..n-1]. Каждую из этих двух половинок в свою очередь разобьем пополам, посчитаем и сохраним сумму на них, потом снова разобьем пополам, и так далее, пока текущий отрезок не достигнет длины 1. Иными словами, мы стартуем с отрезка [0..n-1] и каждый раз делим текущий отрезок надвое (если он ещё не стал отрезком единичной длины), вызывая затем эту же процедуру от обеих половинок; для каждого такого отрезка мы храним сумму чисел на нём.

Можно говорить, что эти отрезки, на которых мы считали сумму, образуют дерево: корень этого дерева — отрезок [0..n-1], а каждая вершина имеет ровно двух сыновей (кроме вершин-листьев, у которых отрезок имеет длину 1).

Задача


Реализуйте структуру данных, хранящую информацию об N (1 ≤ N ≤ 100000) целых числах A1, ..., AN. Структура должна поддерживать следующие операции.



1) INIT(N) Инициализация числом N. При этом каждому числу Ai присваивается значение 0.

2) MODIFY(pos,value) Значение Apos увеличивается на value, если value ≥ 0, и уменьшается на |value|, если value < 0.

3) FINDSUM(l,r) Вывод в выходной файл суммы a[l]..a[r].



Input

Входной файл содержит не более 100000 операций. Каждая операция описывается в отдельной строке. Описание операции начинается с целого числа от 1 до 3 --- ее номера в списке выше. Далее следуют параметры операции в порядке их перечисления в скобках. Числа в каждой строке разделены пробелами.

Все операции корректны. Это значит, что:
  • операция INIT является самой первой операцией во входном файле и больше нигде в нем не встречается;
  • для операции MODIFY выполняются ограничения 1 ≤ pos ≤ N и -10000 ≤ value ≤ 10000;
  • для операции FINDSUM выполняются ограничения 1 ≤ l ≤ r ≤ N.
Output




Выполните операции в порядке их перечисления в входном файле. Если для выполнения операции нужно вывести некоторую информацию в выходной файл, то выведите эту информацию. Вывод для каждой операции оформите в отдельной строке.

Ввод

1 5
2 4 3
2 2 2
3 2 3
2 5 -2
3 2 4
2 5 6
2 4 2
3 3 3
2 1 -8
2 5 -3
2 4 -7
2 5 -4
3 4 4
3 1 2

Вывод

2
5
0
2
6

Решение

Совершенно очевидно, что надо применять дерево отрезков для решения этой задачи. Каждый из запросов задается первым числом в строке входного файла. Т.е. если нам ввели 1, то надо выполнить запрос INIT, если ввели 2, то надо выполнить запрос MODIFY, если 3, то запрос FINDSUM. Итак рассмотрим каждый из запросов в отдельности.

Запрос INIT(N)

Здесь нам надо обнулить всё дерево, т.е. построить его. Для этого сделаем вот что:

Прочитаем число n. Далее подберем такой показатель степени (банально мы подбираем число), чтобы при возведении 2 в эту степень полученное число было больше нашего n. Это и будет размером нашего массива для хранения дерева сумм. Ну и обнуляем все a[i].

Запрос MODIFY(pos,value)

Этот запрос получает на вход индекс pos и значение value, и перестраивает дерево отрезков таким образом, чтобы оно соответствовало новому значению a[pos]=value .
Тогда понятно, что запрос обновления можно реализовать как рекурсивную функцию: ей передается текущая вершина дерева отрезков, и эта функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того, который содержит позицию pos в своем отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков (т.е. как сумма значений по обоим сыновьям текущей вершины).

Запрос FINDSUM(l,r)

Реализация

Построение

 
procedure init;
begin
  readln(n);
  pr:=1;
  while pr<n do
    pr:=pr*2;
end;
 


Обновление

 
procedure modify(p,v:longint);
begin
  a[p]:=a[p]+v;
  if p<>1 then modify(p div 2,v);
end;
 


Нахождение суммы

 
procedure findsum(v,l,r:longint);
begin
  if (lv>r) or (rv<l)
    then exit
      else
        if (l>=lv) and (rv>=r)
          then s:=s+a[v]
            else
              begin
                findsum(2*v,l,(l+r)div 2);
                findsum(2*v+1,(l+r)div 2+1,r);
              end;
end;


В основном коде делаем вот что

 
читаем b
      if b=1 then init;
      if b=2
        then
          begin
            readln(p,v);
            p:=pr+p-1;
            modify(p,v);
          end;
      if b=3
        then
          begin
            readln(lv,rv);
            lv:=pr+lv-1;
            rv:=pr+rv-1;
            findsum(1,pr,2*pr-1);
            writeln(s);
            s:=0;
          end;
    end;

Сообщение отредактировал Санек: 15 ноября 2012 - 09:22






Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных