1

问题是计算小于索引后值的值的数量。这是代码，但我不明白如何使用二叉索引树来做到这一点？

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


}

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

4

2 回答 2

2

要了解 BIT ，这是最好的链接之一。
TC 给出了你使用的函数的完整解释，但剩下的部分是关于如何使用它的逻辑。
基本了解：

问题：有 n 个堆，每个堆最初有 1 块石头，然后我们将 u 到 v 的石头加起来……找出给定堆中有多少石头。

每次迭代都有答案的解决方案是http://pastebin.com/9QJ589VR。在你理解它之后，尝试实施你的问题。

于 2014-01-21T07:07:05.020 回答
0

可以在此处找到二进制索引树背后的更好证明和动机。 https://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

例如，假设您要存储总共 7 个不同元素的累积频率。你可以先写出七个桶，数字将被分配到这些桶中

将表示从存储桶数组更改为节点的二叉树。

如果您将 0 表示“左”，将 1 表示“右”，则每个数字上的剩余位准确地说明了如何从根开始，然后向下走到该数字。

这很重要的原因是我们的查找和更新操作取决于从节点备份到根的访问路径以及我们是跟随左子链接还是右子链接。例如，在查找期间，我们只关心我们遵循的正确链接。在更新期间，我们只关心我们关注的左侧链接。这个二叉索引树只使用索引中的位就可以非常高效地完成所有这些工作。

如果你不关心证明：

我在 BIT 上搜索了傻瓜，发现了这个 https://www.hackerearth.com/practice/data-structures/advanced-data-structures/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&(-x)) ，其更新是必需的或在查找期间需要其值。

在查询时我们沿着数组向下，而在更新时我们沿着数组向上。

例如 query(6) 将在 BIT[6] 处添加总和，但也在 BIT[4] 和 BIT[0] 处添加总和，因为 6(110) - 2 = 4(100) - 4 = 0. 6(110 ) 的最后一位是 2(10)。因此我们做6-2。4(100) 的最后一位是 4(100)。因此我们做4-4。我们在 x==0 时停止。

使用相同的更新逻辑只是添加，不要减去。一次试跑应该足以让你相信它真的很神奇！BIT也是基于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;
    }
于 2021-09-09T17:07:23.287 回答