georgeee Oct 24 2011 at 13:19

Двумерное дерево отрезков (с групповой модификацией элементов)

4 min

16K

Algorithms*

From sandbox

+18

Comments 11

AlexeiKozlov Oct 24 2011 at 13:59

а спроецировать на sql?
я много видел таких статей и сам занимался этими деревьями.
у Вас, сухой пересказ теории по моему разумению.

georgeee Oct 24 2011 at 14:14

На SQL? Можете попробовать, но данная статья писалась в первую очередь для тех, кто интересуется олимпиадным программированием.

И буду благодарен если скинете одну хотя бы из этих статей. Не про дерево отрезков в целом, а именно про двумерный его случай с групповыми операциями. Именно это мне найти в интернете так и не удалось)

xXxVano Oct 25 2011 at 16:08

Не про проецирование на sql, но для олимпиадников и про двумерный случай в том числе читать тут.

georgeee Oct 25 2011 at 16:13

В самом начале
Здесь я разберу обобщение дерева отрезков на двумерный случай, причем (в отличие от этой статьи) рассмотрю реализацию дерева именно с поддержкой групповой модификации элементов.

Ссылка та же самая)

xXxVano Oct 25 2011 at 23:27

Да, вы правы, пост прочитал, а вот по ссылку не заглянул)))

bfDeveloper Oct 25 2011 at 01:02

Отлично подойдёт для вот этого конкурса. Только на сколько я понимаю памяти понадобится много.

georgeee Oct 25 2011 at 06:01

Не, не думаю. Там задача формулируется что надо найти максимальную сумму на уже данной матрице, а дерево отрезков используется именно когда помимо запросов суммы нам нужно обрабатывать запросы модификации

gasya Oct 25 2011 at 11:26

Насколько могу судить по личному опыту, намного чаще приходится работать с набором сильно разреженных точек на плоскости, нежели с фиксированной матрицей.

Думаю было бы полезно добавить обобщение решения задачи на случай точек на плоскости, а так конечно все по существу.

georgeee Oct 25 2011 at 12:31

М… не могли бы вы скинуть пример такой задачи? Просто кроме той задачи, ссылку на которую я дал в конце статьи я не видел задач на эту структуру.

gasya Oct 26 2011 at 09:41

Я пришлю вам на днях пару ссылок, сразу и не вспомню где именно я сталкивался с несколькими подобными.

georgeee Oct 26 2011 at 15:58

Буду весьма благодарен, а если еще и разберусь с тем материалом, то можно еще статейку написать, в дополнение к этой:)

Show the best of all time