Описание тега fenwick-tree

Вопросы с тегом
Дерево Фенвика (или двоичное индексированное дерево) - это быстрая структура данных для хранения и поддержки сводных таблиц частот.
1 ответ

SPOJ DQUERY: TLE даже с битом?

Вот проблема, которую я хочу решить, я использую The Fact That Prefix Sum[i] - Prefix Sum[i-1] Приводит к тому, что частота становится больше нуля, чтобы идентифицировать отдельные цифры, а затем я устраняю частоту, но даже с BIT я получаю TLE Дана …
26 дек '14 в 10:53
1 ответ

Длина самой длинной цепочки сбалансированных скобок в заданных диапазонах

Во-первых, определите строку "сбалансированных" скобок как строку, такую, что для каждого "(" есть один уникальный, соответствующий ")" где-то после этого "(". Например, следующие строки все "сбалансированы": () () () (()) () пока это не так: ) ( ()…
28 окт '14 в 05:48
6 ответов

Можно ли запросить количество различных целых чисел в диапазоне в O(LG N)?

Я прочитал несколько учебных пособий о двух общих структурах данных, которые могут обеспечить обновление диапазона и запрос в O(LG N): Сегментное дерево и Двоичное индексированное дерево (BIT / Fenwick Tree). Большинство примеров, которые я нашел, к…
30 сен '16 в 08:53
2 ответа

Алгоритм времени O(klogn), чтобы найти k-й наименьший элемент из дерева Фенвика

Я имею в виду, чтобы найти kth наименьшая фактическая частота в Fenwick-Tree в O(k log(n)) время.Если мои данные: Tree = [1,3,1,10,3] Actual frequency = [1,2,1,6,3] Таким образом, второй наименьший элемент будет по индексу 1.
12 июл '13 в 23:10
0 ответов

Каков наиболее оптимальный способ решения этой проблемы?

Я видел этот вопрос по кодированию на онлайн-конкурсе по кодированию, но не смог найти наиболее оптимального решения. Вот вопрос:"Вам дан массив A из N целых чисел и Q запросов. Каждый запрос имеет следующий тип:1 pos val: обновить элемент в индексе…
15 фев '19 в 11:02
1 ответ

Максимальная сумма неубывающей подпоследовательности в массиве с использованием дерева Фенвика или BIT

Как мы можем найти максимальную сумму неубывающей подпоследовательности в массиве, используя дерево Фенвика? Например, у нас есть 1 4 4 2 2 3 3 1, здесь максимальная сумма неубывающей подпоследовательности равна 11 (1 2 2 3 3).
04 мар '13 в 02:05
4 ответа

MySQL: принуждение запроса использовать индексы с локальной переменной в предложении WHERE

контекст У меня есть приложение, которое выбирает взвешенную случайную запись из таблицы, для которой суммирование префиксов (весов) является важной частью. Упрощенное определение таблицы выглядит так: CREATE TABLE entries ( id INT NOT NULL PRIMARY…
06 апр '15 в 16:40
5 ответов

Как эффективно умножить диапазон значений массива на заданное число?

Наивным способом было бы линейно итерировать диапазон и умножать на каждое число в диапазоне. Пример: массив: {1,2,3,4,5,6,7,8,9,10}; Умножьте индекс 3 на индекс 8 с 2. Предполагая один основанный индекс. Массив результатов должен быть: {1,2,6,8,10,…
05 июл '15 в 19:08
1 ответ

Дерево Фенвика Ява

Я пытался реализовать Fenwick Tree на Java, но не получил желаемого результата. Вот мой код: import java.io.*; import java.util.*; import java.math.*; class fenwick1 { public static int N; public static long[] a; public static void main(String[] arg…
10 окт '14 в 12:55
2 ответа

Как использовать двоичное индексированное дерево для подсчета количества элементов, которое меньше значения в индексе?

Проблема состоит в том, чтобы посчитать количество значений меньше значения после индекса. Вот код, но я не могу понять, как двоичное индексированное дерево было использовано для этого? #include <iostream> #include <vector> #include <…
20 янв '14 в 12:39
4 ответа

Как эффективно найти непрерывный диапазон используемых / свободных слотов из дерева Фенвика

Предположим, что я отслеживаю использование слотов в дереве Фенвика. В качестве примера, давайте рассмотрим отслеживание 32 слотов, что приведет к макету дерева Фенвика, как показано на рисунке ниже, где числа в сетке указывают индекс в базовом масс…
12 ноя '13 в 18:12
2 ответа

Как узнать, какая позиция имеет префикс M в BIT?

Предположим, я создал двоичное индексированное дерево с префиксной суммой длины N. Основной массив содержит только 0с и 1s. Теперь я хочу найти, какой индекс имеет префиксную сумму M(это означает, что точно M 1с). Как мой массив a[]={1,0,0,1,1}; Пре…
05 апр '17 в 06:12
1 ответ

Умножение с использованием дерева Фенвика

Мы можем выполнить обновление в дереве фенвиков, например, добавив значение и умножив его на значение. У меня есть следующий код для добавления значения х к элементу в позиции л. while(l <= n-1) { tree[l] = tree[l] + x; l = l + (l&(-l)); } То…
08 июл '15 в 06:50
0 ответов

SPOJ D-Query, BIT, но как?

Я пытаюсь решить проблему D-запроса на Spoj. http://www.spoj.com/problems/DQUERY/ Я думаю об установке и запоминании результата, но это действительно медленно. Так что я думал о том, что дерево с двоичными индексами может помочь мне получить lgN за …
25 дек '13 в 11:41
2 ответа

Как выполнить обновление диапазона в двоичном индексированном дереве или дереве Фенвика?

Я пытаюсь решить эту проблему в UVA с помощью Binary Indexed Tree: Problem H Ahoy, Pirates! Input: Standard Input Output: Standard Output In the ancient pirate ages, the Pirate Land was divided into two teams of pirates, namely, the Buccaneer and th…
05 авг '13 в 18:33
1 ответ

Сжатие координат в дереве Фенвика

Допустим, у нас есть n пустых коробок подряд. Мы собираемся положить m групп монет в несколько последовательных коробок, которые известны заранее. Мы помещаем 1-ю группу монет в коробки от i_1 до j_1, 2-ю группу в коробки от i_2 до j_2 и так далее. …
08 май '14 в 06:30
1 ответ

Считать количество точек в левом нижнем квадранте?

У меня проблемы с пониманием решения алгоритмической проблемы В частности, я не понимаю, как или почему эта часть кода s += a[i]; total += query(s); update(s); позволяет вычислить общее количество точек в нижнем левом квадранте каждой точки. Может к…
17 май '14 в 04:28
1 ответ

Найти общее количество возрастающих подпоследовательностей длины k

Предположим, у меня есть массив 1,2,2,10. Увеличивающиеся подпоследовательности длины 3 составляют 1,2,4 и 1,3,4(на основе индекса). Итак, ответ 2. Проблема ССЫЛКА Я хочу лучшее решение с использованием дерева BIT, которое могло бы улучшить мое реше…
14 дек '14 в 06:52
1 ответ

Можно ли построить дерево Фенвика в O(n)?

Дерево Фенвика - это структура данных, которая допускает два вида операций (вы можете дополнить их большим количеством операций): обновление точки update(index, value) сумма префикса query(index) Обе операции находятся в O(log(n)) где n это размер …
26 июн '15 в 08:32
1 ответ

RMQ с использованием двух деревьев Фенвика (двоичное индексированное дерево)

Основываясь на этом документе, я обнаружил, что для выполнения RMQ достаточно использовать два BIT. O(lg N), поскольку его легче кодировать, чем сегментированное дерево, и в документе утверждается, что оно работает лучше, чем другие структуры данных…
09 мар '17 в 02:54