Описание тега segment-tree
A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time.
2
ответа
Как я могу реализовать деревья сегментов с ленивым распространением?
Я реализую дерево сегментов, чтобы иметь возможность быстро отвечать на следующие запросы в массиве A: запрос i, j: сумма всех элементов в диапазоне (i,j) обновить i, j, k: добавить k ко всем элементам в диапазоне (i,j) Вот моя реализация: typedef l…
04 ноя '12 в 11:36
6
ответов
Можно ли запросить количество различных целых чисел в диапазоне в O(LG N)?
Я прочитал несколько учебных пособий о двух общих структурах данных, которые могут обеспечить обновление диапазона и запрос в O(LG N): Сегментное дерево и Двоичное индексированное дерево (BIT / Fenwick Tree). Большинство примеров, которые я нашел, к…
30 сен '16 в 08:53
1
ответ
Исключение выдается при передаче параметров
Я получаю ошибку Exception thrown at 0x009523B9 in Project5.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00E42ED4). в приведенной ниже программе прецедент: 5 1 2 3 4 5 1 Q 2 4 Я получаю ошибку при выполнении этой строки struct node que…
27 янв '19 в 08:12
3
ответа
Оптимизация или Новый алгоритм для решения этой проблемы?
Я пытаюсь решить эту проблему: Маленькая девочка имеет массив из n элементов (элементы массива индексируются начиная с 1). Также есть запросы "q", каждый из которых определяется парой целых чисел li, ri (1 ≤ li ≤ ri ≤ n). Для каждого запроса нужно н…
18 июн '13 в 13:56
1
ответ
Сегментное дерево: количество чисел меньше x
Я пытаюсь решить эту проблему. Я нашел учебник по этой проблеме, но я не понимаю, как построить дерево сегментов, которое будет находить количество чисел меньше x в O(log n) (x может измениться). В учебнике это было опущено. Может кто-нибудь объясни…
06 янв '15 в 12:08
1
ответ
Зачем получать этот код с минимальным диапазоном запросов?
Я пытался решить очень простую проблему, которая просто включала реализацию Range Minimum Query. Ссылка на проблему https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/ Но я превышаю срок. Пожалуйста,…
04 авг '17 в 02:21
0
ответов
Каков наиболее оптимальный способ решения этой проблемы?
Я видел этот вопрос по кодированию на онлайн-конкурсе по кодированию, но не смог найти наиболее оптимального решения. Вот вопрос:"Вам дан массив A из N целых чисел и Q запросов. Каждый запрос имеет следующий тип:1 pos val: обновить элемент в индексе…
15 фев '19 в 11:02
0
ответов
Сглаживание дерева и нанесение на него Сегментного дерева
Предположим, что я нахожу время прибытия и отправления всех узлов в моем графе (N-арное дерево), как тогда применить к нему дерево сегментов, учитывая, что мне нужно отвечать на запросы, которые требуют нахождения суммы значений, связанных со всеми …
30 май '18 в 05:41
1
ответ
Ошибка Seg из-за malloc в конце программы C++
Программа использует деревья сегментов, чтобы найти сумму заданного диапазона запроса. Это дает правильные ответы на введенные данные. Однако в конце программы после выполнения всех строк из главной функции отображается ошибка сегментации. Ссылка на…
03 июн '18 в 07:30
2
ответа
Сегмент дерева мин и макс
Я пытаюсь построить дерево сегментов, родительский узел которого должен содержать минимальное и максимальное значения его дочерних узлов. Теперь, когда я пытаюсь реализовать это, я сталкиваюсь с ошибкой, которая заключается в том, что один дочерний …
07 янв '18 в 12:22
2
ответа
Сегмент дерева памяти
Я видел много реализаций деревьев сегментов, которые используют O(4*N) памяти. Есть ли в любом случае для дерева сегментов использовать ровно 2*N-1 памяти? Я не могу найти реализацию, которая делает это. Даже если они говорят о сложности пространств…
29 авг '16 в 15:17
4
ответа
Умножение в диапазоне
У меня есть массив до 10 чисел, за исключением A[10] = {1,2,3,4,5,6,7,8,9,10}, и я должен вычислить умножение чисел в определенном диапазоне, но не получаю правильный ответ, я использую дерево сегментов и не знаю, как использовать операцию запроса В…
03 авг '13 в 05:15
0
ответов
Вариация проблем с укладкой коробки
Некоторое время я пытался решить следующую проблему конкурса: Вы хотите построить башню как можно выше из N кирпичей. Каждый кирпич представляет собой кубоид с квадратным дном, а башня представляет собой набор кирпичей, сложенных друг на друге. Чтоб…
18 янв '18 в 19:06
0
ответов
Как использовать деревья сегментов, чтобы найти два наименьших числа и одно максимальное число в диапазоне в несортированном массиве?
В настоящее время я использую дерево сегментов, чтобы найти самое маленькое и самое большое число в диапазоне в несортированном массиве, сравнивая и сохраняя самый маленький и самый большой из подмассивов. Тем не менее, я запутался в том, какую инфо…
17 июн '18 в 14:35
0
ответов
Вопрос о сегментном дереве: спой вопрос QUERYIT_SLIS
Вот ссылка на постановку задачи. https://www.spoj.com/problems/QUERYIT/ У меня возникли проблемы с кодированием этой проблемы. Я знаю, что должен использовать сегментное дерево, но реализация мне не ясна.
07 янв '19 в 12:05
1
ответ
Есть ли способ найти частоту числа в данном диапазоне, используя дерево сегментов?
Предположим, у меня есть массив [1, 2, 3, 5, 5, 6, 5, 5] Теперь может быть два вида операций. Одной из них является операция "обновления", то есть увеличение значения в индексе 4[индексирование на основе 1] на X. Другая операция - операция "запрос",…
18 авг '17 в 13:56
1
ответ
Как решить взвешенный выбор активности с использованием деревьев сегментов и двоичного поиска?
Дано N рабочих мест, где каждая работа представлена следующими тремя ее элементами. 1) Время начала 2) Время окончания. 3) Прибыль или стоимость, связанная. Найдите подмножество работ с максимальной прибылью, чтобы в подмножестве не перекрывались …
12 июл '15 в 17:49
2
ответа
Реализация дерева сегментов в Python
Я решаю эту проблему с помощью дерева сегментов, но получаю ошибку ограничения времени. Ниже мой необработанный код для минимального диапазона запроса и путем изменения min в max в моем коде вышеупомянутая проблема может быть решена. Я не знаю, как …
11 дек '16 в 11:18
2
ответа
Сегментное дерево: Ленивое распространение
В массиве целых чисел (размер 10^5) операции похожи на эти... Выполните побитовую операцию xor с каждым элементом от индекса L до R определенным числом X Найти сумму чисел от индекса L до R. Как я могу сделать это с сегментным деревом и ленивым расп…
11 ноя '12 в 17:04
2
ответа
Codeforces Round 671 Div 1 C (абсолютная странность массива)
Codeforces 671 Div 1 C (абсолютная странность массива) Пусть vi будет b1, b2, b3...bk. Обратите внимание, что наша l - r должна покрывать как минимум k - 1 из этих индексов. l должен быть меньше или равен b2. Я смог понять первую часть решения, но к…
18 май '16 в 07:20