问题是计算值小于索引后值的值的数量。这是代码，但我不明白如何使用二进制索引树来执行此操作？
#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;
}
如果有人可以解释代码的工作原理。
要理解这是最好的链接之一。
TC给出了您使用的功能的完整解释，但其余部分是如何使用它的逻辑。
为了基本理解：
ques：有n个堆，在每个堆中，有1个石头，然后我们从U到V添加石头……找到给定堆中有多少石头。
解决方案，每次迭代时都有答案是http://pastebin.com/9qj589vr。理解后，尝试实现您的问题。
在这里可以找到二进制索引树背后的更好的证据和动机。https://cs.stackexchange.com/questions/10538/bit-what-what-is-the-intuition-behind-a-binary-indexed-tree-tree-tree-and-how-was-was-it-thought-a
让我们假设您要存储总共7个不同元素的累积频率。您可以通过写出七个存储桶开始，将数字分配到其中
。将表示形式从一个存储库变为节点的二进制树。
如果您对待0表示"左"。1表示"正确"每个数字上的其余部分拼出了如何从根部开始，然后走到该数字。
这很重要的原因是我们的查找和更新操作取决于从节点返回到根的访问路径以及我们关注左还是右子链接。例如，在查找过程中，我们只是在乎我们遵循的正确链接。在更新期间，我们只是在乎我们遵循的左链接。此二进制索引树通过仅使用索引中的位来实现所有这些超级有效。
如果您不在乎证明：
我用谷歌搜索假人并找到了这个https://www.hackerearth.com/practice/data-snctentures/advanced-data-scruptures/fenwick-binary-indexed-trees/tutorial/
完美二进制树的特性： Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.
为什么要隔离最后一个？
当我们隔离最后一个位时，索引x仅转到索引（（/-）x＆amp;（ - x）），其更新为必要或在查找过程中需要其值。
查询时，我们会沿着数组降低，而更新时，我们会上阵列。
例如，查询（6）将在位[6]添加总和，但也将在位[4]和位[0]添加总和，因为6（110）-2 = 4（100）-4 = 0。6（110）的最后一位是2（10）。因此，我们做6-2。4（100）的最后一位是4（100）。因此，我们做4-4。我们在x == 0时停止。
使用相同的逻辑进行更新，只是添加，不要减去。一项干燥的跑步应该足以说服您真的很神奇！位是基于1的。
public static void update(int x, int val, int size){
//int k =x;
x++;
for (; x<size; x+= x&(-x))
BIT[x]+=val;
}
public static int query(int x){
//int k =x;
int toreturn =0;
for (; x >0; x-= x&(-x))
toreturn+=BIT[x];
return toreturn;
}
public static List<Integer> countSmaller(int[] nums) {
// will only work for positive numbers less that 7.
// I arbitrarily set the size to 7, my code my choice
int size = 7;
BIT = new int[size];
List<Integer> result = new ArrayList<Integer>();
for (int i =nums.length-1; i >=0; i--) {
int smaller_count = query(nums[i]);
result.add(smaller_count);
update(nums[i], 1, size);
}
Collections.reverse(result);
return result;
}