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

Проблема состоит в том, чтобы посчитать количество значений меньше значения после индекса. Вот код, но я не могу понять, как двоичное индексированное дерево было использовано для этого?

#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
#define MOD 1000000007
#define MAXN 10
using namespace std;
typedef pair<int, int> ii;
int BIT[MAXN+1];
int a[MAXN+1];
vector< ii > temp;
int countSmallerRight[MAXN+1];
int read(int idx) {
int sum = 0;
while (idx > 0) {
sum += BIT[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(int idx, int val) {
while (idx <= MAXN) {
BIT[idx] += val;
idx += (idx & -idx);
}
}
int main(int argc, const char * argv[])
{
int N;

scanf("%d", &N);

for (int i = 1; i <= N; i++) {
scanf("%d", &a[i]);
temp.push_back(ii(a[i], i));
}

sort(temp.begin(), temp.end());
countSmallerRight[temp[0].second] = 0;
update(1, 1);
update(temp[0].second, -1);

for (int i = 1; i < N; i++) {
countSmallerRight[temp[i].second] = read(temp[i].second);
update(1, 1);
update(temp[i].second, -1);
}
for (int i = 1; i <= N; i++) {
printf("%d,", countSmallerRight[i]);
}putchar('\n');return 0;}

Было бы полезно, если бы кто-то мог объяснить рабочий принцип кода.

0

Решение

понять БИТ этот это одна из лучших ссылок.
TC дает полное объяснение функций, которые вы использовали, но остальная часть — логика того, как его использовать.
Для базового понимания:

Задание: есть n куч, и в каждой куче изначально есть 1 камень, затем мы добавляем камни от u к v… найдите, сколько камней в данной куче.

решение с ответом на каждой итерации http://pastebin.com/9QJ589VR.
После того, как вы это поймете, попробуйте реализовать свой вопрос.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]