algorithm - 使用查询更新数组

Question

最初有 N 个学生，他们的分数都是 0。现在我们在每个查询中给出 Q 查询，我们将 A 索引学生的分数增加 B。现在重新排列学生我增加排名即最高分将是一，第二最高第二等等...

对于每个学生，他或她的位置等于分数更多的学生数增加 1。

让我们定义hash of participant 作为他/她的位置和点数的乘积。每次查询后，找到参与者哈希的sum

例如:

N=4 Q=4
3 100
2 60
1 80
2 20
1 20

After the first query, participant 3 has 100 and is 1, with hash equal to 
100. The sum of hashes is 100+0+0+0=100


After the second query, participant 2 has the second place with 60 and hash 
120, in total 100+120+0+0 = 220


After the third query, the Rank looks like follows: 
(100,80,60,0). The sum of hashes is 200+160+180+0= 440

In the fourth query participant  the rank is (100,80,80,0) then, with the sum 
100⋅1+80⋅2+80⋅2+0⋅4=420.

我们如何才能有效地做到这一点，一个简单的方法是找到索引并替换它:

while(Q>0){
    Q--;
    int a = in.nextInt()-1;
    long b = in.nextInt();
    if(score.size()==0){
        score.add(b);
        A[a]=b;
        System.out.println(b);
    }else{
        int index =-1;
        if(A[a]!=0){


            int s =0;
            int e = score.size()-1;
            while(s<=e){

                int mid = (s+e)/2;
                if(score.get(mid)==A[a]){
                    index = mid;
                    break;
                }else if(score.get(mid)>A[a]) s = mid+1;
                else e = mid-1;
            }
        }
        A[a]+=b;
        int replace= score.size();
        int s =0;
        int e = score.size()-1;
        while(s<=e){

            int mid = (s+e)/2;
            if(score.get(mid)>A[a]) s = mid+1;
            else{
                replace = mid;
                e = mid-1;
            }
        }

        score.add(replace,A[a]);
        if(index!=-1) score.remove(index+1);


        long o= score.get(0);
        long prev =1;
        for(int i=1;i<score.size();i++){

             if(score.get(i)!=score.get(i-1)){

                  prev =i+1;
                  o+=score.get(i)*prev;
             }else o+=score.get(i)*(prev);

        }
        System.out.println(o);



    }
}

我们如何通过使用线段树或任何其他数据结构更有效地做到这一点。

Answer 1

您的解决方案中较慢的部分是您在每次查询后重新计算散列 (O(N*Q))。

为了让它更快，您需要尽可能多地重用以前的结果。因此，让我们看看查询后哈希和发生了什么。

假设您选择位置 x 的学生并将他在有序列表中移动到位置 y(通过增加分数)。对于哈希和:

• 到 y-1 的部分总和保持不变(那里没有变化)。
• x+1 之后的部分和保持不变(那里没有变化)。
• 您需要减少 xold_score 并添加 ynew_score 以说明学生变动。
• 对于介于 y 和 x-1 之间的学生，他们变成 y +1...x。所以对于哈希和需要增加他们分数的总和。

所有这些操作最多可以在 O(logN) 内完成，以将整体复杂度降低到 O(QlogN)(更好)。

因此，您需要一种数据结构，允许您以 O(logN) 或更短的时间插入、删除和计算部分和。我建议使用平衡二叉树(或跳跃列表)。每个节点都应该跟踪下面有多少个节点以及它们的分数之和是多少。要找到第 x 个元素，您可以使用节点数，而要找到总和，您可以使用部分和。

使用这棵树，您无需更改节点的索引(当您在节点前面插入内容时，它们会自动更改)。如果你想用线段树来做，你需要非常小心，因为移动节点。

例子:

假设分数的当前状态看起来像 [100, 90, 80, 70, 60, 50, 40, 30]。下一个查询是 5 35，所以我们找到了第五个元素(得分为 60 的元素，您可以使用节点下方的元素数来找到它来指导您的搜索)并将其增加 35。之后增加的分数将是 95，因此它进入第二个位置(您可以通过在二叉搜索树中查找值来找到它)。所以 x 是 5，y 是 2。hashsum 更新是 hashsum += 95 * 2 - 60 * 5 + (90+80+70)。您可以使用提到的部分和在二叉树中找到最后的和。