c++ - 如何使用二叉索引树来计算小于索引值的元素数？

Question

问题是计算小于索引后值的值的个数。这是代码，但我不明白如何使用二叉索引树来执行此操作？

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


}

如果有人能解释代码的工作原理，那将会很有帮助。

Answer 1

了解BIT this是最好的链接之一。
TC 给出了你使用的功能的完整解释，但其余部分是如何使用它的逻辑。
基本理解:

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 . 理解之后，尝试实现你的问题。