是否有一个算法来寻找其总和小于给定K的子列表的数量？优于O（N^2）

Question

示例：

Sublists where sum is smaller than given K (K is the maximum sum).
[-1, 1, -2, 1, -1,]
N = -1

[-1, 1, -2]
[-2]
[-2, 1, -1]
[-1, 1, -2, 1, -1]

有四个。你知道吗

我已经找到了这方面的算法，但它们只涉及非负数。你知道吗

谢谢。你知道吗

（例如：https://www.geeksforgeeks.org/number-subarrays-sum-less-k/这是我需要的，但是那里的算法不适用于负数）

Answer 1

设原始数组为A，并生成一个累加和数组S，使得S[i]=A的前i个元素的和。注意，S将比A长一个元素。你知道吗

现在，对于从A[i]到A[j]的每个子列表，其元素之和是S[j+1]-S[i]

为了得到您的答案，我们需要做的就是用i<；j和S[j]-S[i]<；K计算S中索引对（i，j）的数目

您可以使用顺序统计树：https://en.wikipedia.org/wiki/Order_statistic_tree

这是一个二叉搜索树，其中增加了每个子树大小的记录，可以让您在O（logn）时间内回答“有多少个条目有值<；=x”之类的问题。你知道吗

从树为空开始，然后：

for j=1 to S.length-1:
    add S[j-1] to the tree
    query for the number of elements in the tree with values > S[j] - K
    add that count to the total

总复杂度为O（N logn）（其中N是输入的大小！），由树中每个j的O（logn）添加和查询操作控制。你知道吗

Answer 2

如果你的列表包含负数，不求每个成员的和就不可能知道它们的和。你知道吗