Warning: Illegal string offset 'html' in /var/www/lvp37/data/www/lvp37.ru/cache/skin_cache/cacheid_1/skin_topic.php on line 909
Дерево отрезков - олимпиадники-информатики

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


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


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

#1 Санек

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

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

Отправлено 14 November 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 November 2012 - 09:22


#2 StepPemia

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • ГородDuverge

Отправлено 08 March 2020 - 23:42

Zithromax Treats What online cialis Kamagra Oral Jelly How To Take Cialis Viagra 100mg Import Reimport

#3 Georselor

    Новичок

  • Пользователи
  • Pip
  • 0 сообщений
  • ГородBaghdad

Отправлено 09 December 2020 - 16:56

cialis levitra compare diftadarma cialis buy Quokcync viagra riesgos

#4 ScottKic

    Новичок

  • Пользователи
  • Pip
  • 0 сообщений
  • ГородLinguere

Отправлено 19 December 2020 - 13:47

заработок в интернет авто шкипер тату на каких играх можно заработать деньги как выйграть джекпот аватарии скачать бесплатно игры на андроид сабвей серф новая версия много денег онлайн клубы азартных игр на деньги скачать читы на деньги в игру короли улиц опросы игровых сайтов игра за эльфа герои войны и денег бонус код неймар сайты кейсов кс го от 20 рублей инструмент для заработка в интернете деньги распечатать для игры детские картинки заработок в интернете на дому игра короли улиц читы на деньги

любовь амулеты http://santeespoir.o...mi-r-ligu#48639 экономическая игра с выводом денег отзывы http://forum.omnicom...n=profile;u=571 автономная некоммерческая организация содействия прокуратуре http://gymnasium.nef...hp?lookup=21090 игры онлайн бесплатно для девочек гонки 2 http://gymn3saratov....ew#message63084 хостинг для изображение http://stalzashita.r...nfo&user=oreboq

рулетка кс го 30 скачать взломанную игру бой с тенью 2 много денег реклама сайтов кейсов кс го сайт игровой портал втб ржд бонус регистрация распечатать раскраски деньги для игры топ рулеток кс го бесплатных сайт для вывода денег скинами кс го симулятор кейсов cs go бесплатно на компьютер бонус коды на август в вот

игры с выводом денег без платежных баллов http://forum.rucarp....ber.php?u=97507 начисление компенсации за неиспользованный отпуск украина http://bizplan.uz/forum/user/13520/ ставки на спорт догоном http://mv4you.net/in...&user=urexijaqy бонус код на ворд оф варшип http://bigsasisa.org...nfo&user=yfuqoq как считается ставка система в букмекерской конторе http://ladyvoyage.ru...r/214136-ivuzaq

#5 ScottKic

    Новичок

  • Пользователи
  • Pip
  • 0 сообщений
  • ГородLinguere

Отправлено 19 December 2020 - 13:47

кейсы в cs go симулятор онлайн бесплатно купить игру в steam через яндекс деньги игровые автоматы бесплатно и без регистрации с бонусами казино корона рулетка кс го игра сайты с халявой cs скачать бесплатно программу для заработка денег в интернете без вложений скачать программу на деньги артмани на игры взламываем деньги в игре ассасин крид 4 черный флаг халява кс го без депозита сентябрь программ для накрутки денег в играх казино миллион с бонусом за регистрацию игра онлайн динозавры с выводом денег приложение для заработка денег на телефон на русском языке скачивая игры скачать игру real racing 3 много денег на андроид как долго живут игры с выводом денег

амулет пк тула http://intlaw.rudn.r...=new#message878 сайт ставок на баскетбол https://minoxidil4yo...rum/user/21415/ автономная некоммерческая организация центр гражданских инициатив развитие http://www.lfclondon...s/users/azadyq/ онлайн стратегии для смартфонов бесплатно http://karabash.chel...&uname=ydekeweq создать бесплатный teamspeak 3 на хостинге http://xn----dtbingm..._view&UID=18353

игра русская рыбалка за деньги открытие кейсов бесплатно не кс го рулетки в кс го видео смотреть бонус коды для ворлд оф танкс на ставка кс магазин скриптов для рулеток кс го скачать чит на игру блокада на деньги бонус код джойказино 2016 июнь сайты с ежедневными кейсами кс го бесплатно бонус код танк excelsior

как попасть в джекпот в аватарии http://www.gaya.ru/g...isplay&jid=7933 юристы медицинское право http://cp45046.tmweb...new#message8801 лига ставок букмекерская контора мобильная версия вход http://commercialref...sers/eqemuzala/ дополнительный заработок при помощи интернета http://autopiter.myb...wprofile&u=3962 ставки на спорт от профессионалов из англии и сша http://kgti.kg/index...o&user=irylawyj

#6 ScottKic

    Новичок

  • Пользователи
  • Pip
  • 0 сообщений
  • ГородLinguere

Отправлено 19 December 2020 - 13:48

rage джекпоты в источнике скачать игру на андроид зомби ферма много денег стихи о шкиперах скачать игру кср гонки мод много денег нарды игры на реальные деньги wot бонус код 2016 многоразовые игры из которых можно вывести деньги скачать чит деньги для игры варфейс игра моя бимбо много денег игра рыбалка за реальные деньги скачать лучшие экономические игры вулкан официальный с джекпотом заработок в интернете за переходы как сделать деньги в игру euro truck simulator 2 популярные казино с моментальным выводом денег

чери амулет щетки стартера от чего подходят http://http://hmairs...ewprofile&u=606 новые сайты с халявой кс го что это http://fitagrunt.ru/...o&user=onovikaw порядок расторжения брака в загсе и суде http://flooring.kiev...info&user=axizu ігри гонки нід фор спід онлайн http://rnd.minzdravr...um/user/100177/ дешевые хостинги серверов css http://www.hotelforr...username=agulev

сайты где можно зарабатывать деньги без вложений с выводом кейсы в кс го демо версию world of tanks бонус код сентябрь 2015 как зарабатывать настоящие деньги на играх в андроид игры i на деньги бонус как сделать свою кс го рулетку игры как заработать деньги в игре агарио игра демократия деньги теория игр и экономическое поведение читать онлайн список интернет сайтов для заработка

бонус код в доте 2 http://chgard36.tgl....ser/3332-egywax положения о юридических консультациях http://amlpageslubit...profile&u=12706 ставки нба прогнозы http://anapa.net.ru/...sername=ufunipe симулятор кейсов кс го с инвентарем бесплатно http://e-cur.ru/forum/user/554/ слишком высокие ставки читать онлайн бесплатно http://news.coin.su/...ew#message26642





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

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