如何使用二进制索引树来计算元素的比为指标，数值越小多少？ [英] How to use Binary Indexed tree to count the number of elements that is smaller than the value at index?

问题描述

的问题是计算值的数量小于索引后的值。这里是code，但我无法理解二进制索引树被用来做什么呢？

The problem is to count the number of of values less than the value after index. Here is the code, but I can't understand how binary indexed tree has been used to do this?

#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;


}

这将是有益的，如果有人可以解释的code的工作主体。

It would be helpful if someone could explain the working principal of the code.

推荐答案

要了解BIT的这是最好的环节之一。
TC给你使用的功能完整的交代，但是剩下的部分是关于如何使用它的逻辑。
对于基本的了解：

to understand BIT this is one of the best links .
TC gives the full explaination of functions you used , but rest part is logic on how to use it .
For basic understanding :

疑问句：有n个堆并在每个堆最初有1石头那么我们从u加石头到v ...找到多少石头里有给堆。

ques: there are n heaps and in each heap initially there are 1 stones then we add stones from u to v…find how much stone are there in given heap.

解决方案，与答案在每个迭代是 http://pastebin.com/9QJ589VR 。 当你了解它，尝试实现你的问题。

the solution , with answer at each iteration is http://pastebin.com/9QJ589VR. After you understand it , try to implement your question .

这篇关于如何使用二进制索引树来计算元素的比为指标，数值越小多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！