Описание тега binary-indexed-tree

Описание тега Вопросы с тегом
Двоичное индексированное дерево (BIT), также известное как дерево Фенвика, представляет собой расширенную структуру данных на основе дерева, которую можно использовать для хранения и вычисления совокупной суммы или частоты. BIT более эффективен, чем другие структуры данных (например, дерево сегментов и другие RMQ), учитывая временную сложность, сложность памяти и строку кода.
2 ответа

Может кто-нибудь объяснить мне решение "Почти отсортированные интервалы"?

Здесь проблема, и здесь есть решение. Первая часть достаточно проста. Это вторая часть, которую я не понимаю, как бы я ни старался. В основном у вас есть два набора интервалов, и вам нужно найти все пересечения, где один интервал не полностью внутр…
05 авг '14 в 22:28
1 ответ

C++ Подсчет инверсий в массиве, фатальный сигнал 11 (BIT)

Мне дали этот вызов в "классе" программирования. В конце концов я решил использовать решение "Binary Indexed Trees", поскольку о структурах данных мне хотелось бы узнать больше. Внедрение BIT было довольно простым, а после этого - не так уж и много.…
14 дек '18 в 14:44
0 ответов

Как решить проблемы с Binary Indexed Tree?

Этот вопрос звучит очень расплывчато и требует пояснения: Я узнал о двоичном индексированном дереве несколько недель назад. Эта структура данных является блестящим дизайном. На самом деле мне понадобилось очень много времени, чтобы понять, как он по…
02 май '16 в 13:31
2 ответа

Обновление диапазона в двоичном индексированном дереве

Как я могу использовать двоичное индексированное дерево для обновления диапазона, чтобы каждый элемент A[k] в диапазоне говорят [i..j] обновляется до A[k]*c где c некоторая константа. И мне нужно делать точечные запросы после таких операций обновлен…
08 янв '14 в 17:30
1 ответ

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

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

Может кто-нибудь предоставить мне алгоритм двумерного двоичного индексированного дерева?

Я искал в интернете, но не смог найти хороший. Я получил некоторую помощь от geeksforgeeks.org, но не могу понять строительную часть, где мы вычитаем v1-v2-v2-v4+v3 из aux[i][j] при обновлении массива BIT. Просто дайте мне знать, почему мы здесь выч…
26 июл '17 в 17:58
1 ответ

Применение двоичного индексированного дерева

Я пытался решить эту алгоритмическую проблему, и я наткнулся на это хорошее решение: "Идея состоит в том, чтобы обрабатывать ai, bi и ci асимметрично. BIT поддерживает минимальные запросы для ключевых интервалов, начинающихся с 1. Мы используем ci в…
28 май '17 в 07:00
1 ответ

Диапазон XORed сумма с использованием дерева BIT или Fenwick

Для заданного массива целых чисел мы должны вычислить XORed сумма в заданном диапазоне [L, R], от XORed Я имею в виду сумму Σ(Arr[i]^p) где i:[L,R] а также p это какое-то число. Это можно легко сделать при расчете XORed сумма до каждого i-th элемент…
20 мар '17 в 20:41
1 ответ

Не могу понять, что не так с моим решением Binary Indexed Tree

Я решаю проблему. Count of Range Sum Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j),inclusive. Exampl…
20 июл '16 в 22:14
1 ответ

Соответствие скобок с помощью BIT

Редактировать: я пытался решить проблему спой. Вот ссылка на проблему: http://spoj.pl/problems/BRCKTS Я могу думать о двух возможных структурах данных для решения проблемы: одна использует дерево сегментов, а другая - BIT. Я уже реализовал решение с…
27 фев '10 в 20:47
2 ответа

Подсчитать "минимальные" значения

Проблема: У меня есть вход n векторов: (x, y, z): x ∈ {1..n},y ∈ {1..n},z ∈ {1..n} (every "dimension" is set(1..n)) *I mean that in one vector x,y,z can be the same(x=y=z), but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2 v1>v2 if and only if x1>x2,y1…
01 мар '18 в 15:45
1 ответ

Шаг обновления в Fenwick Trees

Мой вопрос касается полного обоснования шага обновления в Binary Indexed Trees (деревья Фенвика). Таким образом, при обновлении нашего массива с определенным приращением в определенной позиции обновление происходит следующим образом: void updateBIT(…
01 авг '18 в 18:35
0 ответов

Как получить счетчик инверсий с обновлением

Счетчик инверсий в данном массиве очень известен с временной сложностью O(NlogN). Однако мне интересно, есть ли способ сделать это с обновлением. Формат ввода: первая строка состоит из целого числа n; вторая строка включает в себя n целых чисел, кот…
02 ноя '17 в 09:17
1 ответ

BIT To Query Для заданного диапазона

У нас есть массив arr[0 .,, н-1]. Мы должны быть в состоянии эффективно найти минимальное значение от индекса qs (начало запроса) до qe (конец запроса), где 0 <= qs <= qe <= n-1 Я знаю данные structure Segment Дерево для этого. Мне интересно, если B…
09 янв '15 в 15:29
0 ответов

Дерево Фенвика для запроса диапазона

Существует вопрос FLIPCOIN о коде шеф-повара, который просит нас ответить на 2 вида запросов. Оба эти запроса являются обновлением диапазона и запросом диапазона. https://www.codechef.com/problems/FLIPCOIN Эти запросы показывают, что мы можем исполь…
08 фев '19 в 04:19
1 ответ

Отвечать на запросы о количестве различных чисел в заданном диапазоне

Эта проблема У меня есть массив с N номерами. Числа могут быть несоответствующими, а также могут быть неупорядоченными. Я должен ответить на Q вопросов о том, сколько различных чисел существует между A и B. Где A, B - индексы между 0 <= A <= B Я зна…
07 янв '18 в 05:52
1 ответ

Найти количество предметов с весом k в диапазоне (с обновлениями и запросами)

Я пытаюсь решить следующую проблему: Учитывая массив элементов с целыми весами (произвольный порядок), мы можем иметь 2 возможных операции: Запрос: Выведите количество элементов весом k в диапазоне от x до y. Обновление: измените вес предмета по опр…
07 дек '16 в 06:05
1 ответ

Дерево двоичного индекса (обновление диапазона и точечный запрос)

Может ли кто-нибудь помочь мне понять в дереве двоичного индекса, когда мы делаем обновление диапазона - Почему нет, мы обновляем каждый элемент, почему только начальный элемент и конечный элемент Например 0 мы должны обновить диапазон элементов мас…
16 июл '16 в 20:08
1 ответ

Сумма дерева Фенвика

Это код для запроса суммы от индекса 0 до индекса X Int query(int x){ Int sum=0; for(; x&gt;0; x -= x &amp;(-x) ) sum += BIT[x]; Return sum; } У меня есть два массива BIT[] and a[], Я храню значения от массива до BIT для запросов. Теперь в соответст…
10 окт '16 в 12:23
1 ответ

Строковый запрос с двоичным индексированным деревом

Я хочу, чтобы диапазон запроса строки с использованием дерева Фенвика. Но что-то не так с моим кодом. Конкатенация выдает ошибку. Ошибка:[Ошибка] не соответствует 'operator+=' (типы операндов: 'std::vector >' и 'std::string {aka std::basic_string}')…
10 июл '17 в 14:21