algorithm - 使用线段树求范围内小于 k 的所有数字的总和

Question

我有一个元素大小 <= 10^6 的数组 A。

我想实现一个数据结构，该结构在特定范围内(例如 l 到 r)为我提供所有元素的总和，谢谢 k。

我知道它可以使用线段树来解决，但不知道如何为变量 k 查询维护线段树。请帮助我伪代码。

由于没有更新，我认为也可以使用 Mo 的算法。

Answer 1

下面假设你的数组中的元素都是positive

如何不为特定的 k 维护线段树？但改为解析查询

只需考虑您的线段树。

在每个节点 Node_i ，你知道:

• 其总和:s_i
• 它涵盖的元素数量:n_i

所以两步:

1. 对于给定的范围查询，下到对应的节点Node_i .
2. 为此Node_i , s_i是其两个子项之和的总和。对于每个给定的 child Node_j及其 n_j涵盖的要素:两种可能性
   • n_j*k < s_j :所有元素都小于k
   • n_j*k >= s_j :至少有一个元素大于或等于k

所以第一种情况， child 的sum已经有效了，不用再做了。

第二种情况，你必须探索 child 等等，直到无事可做为止

在某些时候，(如果你有一个无效元素)你会到达树的底部:那个节点(也是一个元素)是坏的，你回溯这个事实。当你回到你的节点时 Node_i , 你从 s_i 中减去您发现的所有那些坏叶节点的值。

伪代码是:

#node is like: 
#children:[c1, c2]
#n:number of elem covered
#sum: sum of all elemens it covers
#returns the sum of the covered elements whose value is __greater__ or equal than k
def explore(node, k):
    #terminal case
    if node.n == 1:
        if node.sum >= k:
            return node.sum
        # when the range query is of size 1..., 
        # you may want to handle that elsewhere (e.g before calling explore)
        return 0
    end

    #standard case
    [c1,c2] = node.children
    totalsum = 0
    if c1.n * k < c1.sum
        #all your elems are less than k, substract nothing
        totalsum += 0 
    else
        totalsum += explore(c1, k)
    #same for c2...
    return totalsum