Описание тега cartesian-tree
В информатике декартово дерево - это двоичное дерево, полученное из последовательности чисел; он может быть однозначно определен из свойств, что он упорядочен в куче и что симметричный (по порядку) обход дерева возвращает исходную последовательность.
2
ответа
Эффективно преобразовать массив в декартово дерево
Я знаю, как преобразовать массив в декартово дерево в O(N) времени http://en.wikipedia.org/wiki/Cartesian_tree и http://community.topcoder.com/tc?module=Static&d1;=tutorials&d2;=lowestCommonAncestor RMQ в LCA Однако объем требуемой памяти слишком ве…
12 ноя '13 в 05:10
1
ответ
Подход минимального диапазона <O (n), O (1)> (от дерева к ограниченному RMQ)
Итак, я прочитал этот учебник TopCoder по RMQ (Range Minimum Query), и у меня возник большой вопрос. В разделе, где он представил этот подход, я могу понять до сих пор следующее: (В целом подход использует методологию, представленную в алгоритме Spa…
08 фев '13 в 17:08
2
ответа
Как обратить массив из индекса i в индекс j несколько раз, используя декартово дерево?
Предположим, у меня есть заданный массив A. Теперь есть несколько операций вида reverse i,j // means reverse the array Ai..j inclusive а также print i,j Распечатать массив Ai..j. Пример, A = 6 9 1 10 4 15 9 reverse 2,3 A = 6 1 9 10 4 15 9 reverse 3,…
11 окт '14 в 08:07
2
ответа
RMQ на статическом 2D массиве в постоянное время
Ввод представляет собой массив (n*m 1<n,m< 1000), Я должен найти максимальный элемент в каждом подматрице size( a*b ), Я пытался сделать это, повторяя x над n-a+1 а также y над m-j+1, 2D segment trees или же quad tree Это не достаточно быстро,…
07 июн '16 в 15:08
6
ответов
Когда использовать трепан
Может ли кто-нибудь привести реальные примеры того, когда лучшим способом хранения ваших данных является treap? Я хочу понять, в каких ситуациях трэп будет лучше, чем кучи и древовидные структуры. Если это возможно, приведите несколько примеров из р…
15 апр '13 в 06:57
2
ответа
Сложность единичного изменения в массиве, которое поддерживается статическим Range Minimum Query
У меня был тест в курсе структур данных, и один из вопросов был: Допустим, у вас есть массив n-размера, который поддерживается с помощью запроса минимального диапазона, который дает минимум между двумя числами в массиве в o(1) сложности. Конечно, ма…
12 фев '14 в 14:37
1
ответ
рекурсивное дерево с декартовой реализацией
Мне нужна помощь, чтобы найти все комбинированные возможности из дерева Я прочитал много документации о декартовых произведениях, много пробовал, но ни один из них, похоже, не работает должным образом... Это мое дерево var data = [ { "id": 5, "name"…
05 ноя '19 в 13:08