Вопросы по теме 'segment-tree'
Дерево сегментов с ленивым распространением Проблема ограничения времени
Ниже приведена реализация http://www.spoj.pl/problems/LITE/ . использование дерева сегментов с ленивым распространением. Я новичок в сегментировании деревьев и не могу понять, почему я получаю TLE. Может ли кто-нибудь посмотреть на это и помочь...
2114 просмотров
schedule
27.04.2022
отображение данных и ленивое распространение в дереве сегментов
Похоже, во всем Интернете есть только одна хорошая статья о ленивом распространении в дереве сегментов: http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296
Я понял концепцию обновления только узла запроса и маркировки его дочернего элемента. Но...
4286 просмотров
schedule
27.08.2023
В чем разница между деревьями сегментов, деревьями интервалов, деревьями с двоичным индексом и деревьями диапазонов?
Каковы различия между деревьями сегментов, деревьями интервалов, деревьями с двоичным индексом и деревьями диапазонов с точки зрения:
Ключевая идея / определение
Приложения
Производительность / заказ в больших размерах / занимаемое...
40176 просмотров
schedule
25.09.2022
Дерево сегментов с ленивым распространением для кратного 3
Сокращенная задача: вам дан массив из n элементов, изначально все они равны 0.
Вы получите два типа запроса: 0 index1 index2, в этом случае вам нужно увеличить на единицу все элементы в диапазоне index1 index2 (включено).
Второй тип: 1 index1...
1303 просмотров
schedule
18.04.2022
Ближайшие равные числа
Предположим, у вас есть a1..an номеров и несколько запросов [l, k] (1 < l, k < n) . Задача состоит в том, чтобы найти в интервале [l, k] минимальное расстояние между двумя одинаковыми числами.
Примеры: (интервал l,k показан как |...|)...
119 просмотров
schedule
09.09.2022
Сложение, умножение, подстановочные запросы
Дан одномерный целочисленный массив A длины N. Нам нужно Q запросов каждого из следующих типов:
ПРИМЕЧАНИЕ. M фиксируется равным 10^9 + 7 .
Запрос 1 : 1 x y v : Это означает добавление v ко всем элементам от x до y в 1 базовом индексированном...
244 просмотров
schedule
17.02.2023
Поиск максимума с использованием дерева сегментов дает неверные результаты
У меня есть эта реализация дерева сегментов, чтобы найти максимальный элемент в диапазоне:
int TREE[10000000]={0};
int arr[100000];
int RMQ(int ss, int se, int qs, int qe, int index)
{
if (qs <= ss && qe >= se)
return...
192 просмотров
schedule
17.05.2023
Построение дерева сегментов
Учитывая целочисленный массив A из n элементов и m запросов, каждый запрос содержит целое число x, я должен ответить на количество элементов в массиве меньше x. 0 ‹ А[i] ‹ 10^6 && х ‹ 10^6
пример:
A[]={105,2,9,3,8,5,7,7}
запрос
6
8...
237 просмотров
schedule
09.11.2022
метод построения дерева сегментов
Привет, я изучаю дерево сегментов. Построение дерева отрезков рекурсивным методом мне понятно, я реализовал его так:
void build( int n, int b, int e){
if(b > e) return;
else if (b == e) { tree[n] = arr[b]; return }
build(n*2 , b ,...
146 просмотров
schedule
04.06.2023
проверьте, сбалансирована ли строка скобок, выполнив определенную операцию над строкой
Учитывая строку скобок, мы должны выполнить 2 вида операций:
flip- меняет i-ю скобку на противоположную (left->right , right->left)
check- если строка является сбалансированным выражением в скобках
длина строки не более 30000....
505 просмотров
schedule
10.07.2022
Память дерева сегментов
Я видел много реализаций деревьев сегментов, использующих память O(4*N). Может ли дерево сегментов использовать ровно 2*N-1 памяти? Я не могу найти реализацию, которая делает это. Даже если они говорят о сложности пространства на самом деле 2*N-1,...
442 просмотров
schedule
18.04.2022
Обновить один элемент в дереве сегментов
Часть проблемы, которую я решаю, связана с получением минимума в диапазоне массива (RMQ), поэтому я реализовал дерево сегментов, и пока оно работает нормально. Затем я хочу обновить один элемент в исходном массиве (нет обновлений с более чем одним) и...
436 просмотров
schedule
03.12.2023
Можно ли запросить количество различных целых чисел в диапазоне за O (lg N)?
Я прочитал несколько руководств о двух общих структурах данных, которые могут выполнять обновление диапазона и запрос в O (lg N): Дерево сегментов и Двоичное индексированное дерево (BIT/Дерево Фенвика).
Большинство примеров, которые я нашел,...
8915 просмотров
schedule
30.07.2022
Обновление в дереве сегментов
Я изучаю дерево сегментов, я столкнулся с этим вопросом. Существуют операции типа Array A и 2
1. Find the Sum in Range L to R
2. Update the Element in Range L to R by Value X.
Обновление должно быть таким
A[L] = 1*X;
A[L+1] = 2*X;...
1723 просмотров
schedule
01.05.2023
Есть ли способ найти частоту числа в заданном диапазоне с помощью дерева сегментов?
Предположим, у меня есть массив [1, 2, 3, 5, 5, 6, 5, 5]
Теперь может быть два вида операции. Одной из них является операция «обновления», то есть увеличение значения в индексе 4 [индексирование на основе 1] на X. Другая операция — это операция...
140 просмотров
schedule
19.10.2022
Удалите повторяющиеся элементы и дайте сумму диапазона
У меня есть вопрос относительно уже заданного этого вопроса: БИТ?
Что, если я хочу не учитывать повторяющийся элемент при выполнении запроса диапазона? следующий пример:
Input
Line 1: n (1 ≤ n ≤ 10^6).
Line 2: n numbers a1, a2, ..., an...
81 просмотров
schedule
03.06.2023
Как использовать деревья сегментов, чтобы найти два наименьших числа и одно максимальное число в диапазоне в несортированном массиве?
В настоящее время я использую дерево сегментов, чтобы узнать наименьшее и наибольшее число в диапазоне в несортированном массиве, сравнивая и сохраняя наименьший и наибольший подмассивы.
Однако я запутался в том, какую информацию нужно сохранить...
64 просмотров
schedule
23.12.2022
Алгоритм поиска наименьшей цены для прохода через массив
Я много думал о следующей проблеме:
Нам дан массив из n чисел. Мы начинаем с первого индекса, и наша задача — добраться до последнего индекса. При каждом шаге мы можем перейти на один или два шага вперед, и число в индексе, к которому мы...
868 просмотров
schedule
12.11.2022
Не удалось найти дерево сегментов ошибок: минимум в подмассиве
Я новичок в структурах данных и алгоритмах и не могу найти ошибку в своем коде для вопроса.
Минимальный запрос диапазона
Учитывая массив A размера N, есть два типа запросов к этому массиву.
q l r: В этом запросе вам нужно вывести минимум в...
58 просмотров
schedule
27.08.2022
Количество вхождений каждого отдельного целого числа в заданных диапазонах для массива
Дан массив из n целых чисел (n <= 1e6) [a0, a1, a2, ... an-1] (a[i] <= 1e9) и несколько запросов. В каждом запросе задано 2 целых чисел l и r (0 <= l <= r <= n-1) , и нам нужно вернуть количество каждого отдельного целого...
807 просмотров
schedule
26.11.2023
