Публикации по теме 'fenwick-tree'
Двоичное индексное дерево
Двоичное индексное дерево или дерево Фенвика — это мощная структура данных для решения проблем, связанных с обновлением диапазона/запросом диапазона или точечным обновлением/запросом диапазона или обновлением диапазона/запросом точки . Здесь мы обсудим это самым простым способом: P.
Сегодня мы обсудим самую простую форму точечного обновления/запроса диапазона двоичного индексного дерева.
Предположим, у вас есть проблема, когда вам дан массив, и над массивом будут выполняться два..
Вопросы по теме 'fenwick-tree'
Binary Indexed Tree (Дерево Фенвика) — об обновлении
Недавно я изучил структуру данных Дерево Фенвика (двоичное индексированное дерево) .
При запросе я могу понять, зачем вычитать (idx и -idx). Однако я не могу понять, зачем добавлять (idx и -idx) при обновлении значения.
Другими словами, я...
1591 просмотров
schedule
23.03.2023
Найдите общее количество возрастающих подпоследовательностей длины k [дубликаты]
Предположим, у меня есть массив 1,2,2,10.
Возрастающие подпоследовательности длины 3 равны 1,2,4 и 1,3,4 (на основе индекса).
Итак, ответ 2. ССЫЛКА на проблему
Мне нужно лучшее решение с использованием дерева BIT, которое могло бы улучшить...
765 просмотров
schedule
29.06.2022
Требуется четкое объяснение обновлений диапазона и запросов диапазона Двоичное индексированное дерево
Я прошел несколько руководств по обновлению диапазона - запросы диапазона двоичного индексированного дерева. Я не могу понять ни одного из них. Я не понимаю необходимости строить еще одно дерево.
Может ли кто-нибудь объяснить мне это на простом...
2795 просмотров
schedule
10.04.2022
Как эффективно умножить диапазон значений массива на заданное число?
Наивным способом было бы линейное перебор диапазона и умножение на каждое число в диапазоне.
Пример: Массив: {1,2,3,4,5,6,7,8,9,10}; Умножьте индекс 3 на индекс 8 с 2. Предположим, что один базовый индекс.
Массив результатов должен быть:...
1437 просмотров
schedule
06.05.2023
Что означает (число и -число) в битовом программировании?
Например:
int get(int i) {
int res = 0;
while (i) {
res = (res + tree[i]) % MOD;
i -= ( (i) & (-i) );
}
return res;
}
Функция обновления дерева:
void update(int i, int val) {
while (i <= m) {...
4811 просмотров
schedule
01.02.2023
Можно ли запросить количество различных целых чисел в диапазоне за O (lg N)?
Я прочитал несколько руководств о двух общих структурах данных, которые могут выполнять обновление диапазона и запрос в O (lg N): Дерево сегментов и Двоичное индексированное дерево (BIT/Дерево Фенвика).
Большинство примеров, которые я нашел,...
8915 просмотров
schedule
30.07.2022
Как найти, какая позиция имеет сумму префикса M в BIT?
Предположим, я создал двоичное индексированное дерево с суммой префиксов длины N. Основной массив содержит только 0 s и 1 s. Теперь я хочу найти, какой индекс имеет префиксную сумму M (это означает, что он имеет ровно M 1 s).
Как мой массив...
364 просмотров
schedule
07.06.2024
Удалите повторяющиеся элементы и дайте сумму диапазона
У меня есть вопрос относительно уже заданного этого вопроса: БИТ?
Что, если я хочу не учитывать повторяющийся элемент при выполнении запроса диапазона? следующий пример:
Input
Line 1: n (1 ≤ n ≤ 10^6).
Line 2: n numbers a1, a2, ..., an...
81 просмотров
schedule
03.06.2023
