algorithm - 使用分割树的范围内小于k的所有数字的总和

我有一个数组A，元素大小<=10^6。
我想实现一个数据结构，它使我在一个特定的范围内（比如说从k到l）所有元素的总和更少。
我知道可以使用段树来解决这个问题，但不知道如何维护变量r查询的段树。
请帮我处理伪代码。
由于没有更新，我认为Mo的算法也可以使用。

最佳答案

下面假设数组中的元素都是正的
不维护特定k的段树，而是解析查询如何
考虑一下你的片段树。
在每个节点上，您都知道：
覆盖总数：Node_i
它包含的元素数：s_i
所以有两个步骤：
对于给定的范围查询，转到相应的节点n_i。
因此，Node_i是它的两个孩子的总和。对于每一个包含其Node_i元素的给定子s_i来说：两种可能性
Node_j：所有元素都小于k
n_j：至少有一个元素大于或等于n_j*k < s_j
所以第一种情况是，孩子的金额已经有效，没什么可做的了。
第二种情况，你必须探索孩子等，直到无事可做
在某个点上（如果你有一个无效的元素），你会到达树的底部：这个节点（也是一个elem）是坏的，你会回溯这个事实。
当您返回到节点n_j*k >= s_j时，您将从k减去找到的所有叶节点的值。
伪代码是：

#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

关于algorithm - 使用分割树的范围内小于k的所有数字的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58293297/