如何在恒定时间内从给定的索引间隔（i，j）中找到元素的总和？
给定一个数组。我们如何(i, j)在恒定时间内找到索引间隔中的元素总数。允许您使用额外的空间。
示例：
A：3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1
长度= 14
int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);
固定时间之和应为10。
问题答案：
如果您可以花费O（n）的时间来“准备”辅助信息，那么您就可以基于该信息来计算O（1）中的总和。
准备（O（n））：
aux[0] = 0;
foreach i in (1..LENGTH) {
aux[i] = aux[i-1] + arr[i];
}
查询（O（1））arr从编号1为LENGTH：
sum(i,j) = aux[j] - aux[i-1];
我认为这是意图，因为否则，这是不可能的：对于任何人来说length，sum(0,length-1) 您都应该扫描整个阵列；至少需要线性时间。
-
我试图解决以下问题：给定N个时间间隔，每个时间间隔指定为（开始，结束），不重叠，根据开始排序——找到一个包含给定日期的时间间隔。例如： 3人进入第一节，15人进入第四节，以此类推。 到目前为止，我有以下基本想法： 我们可以使用二进制搜索来找到相应的间隔（logn） 由于可能只有少数时间间隔较大，其余时间间隔较小，因此根据时间长短对itervals进行排序可能是值得的。然后，在统计上，大多数情况下，
-
间隔有开始和结束时间。间隔可能重叠。可能有几个包含时间t的间隔。只返回其中一个就可以了。 这是一个面试问题。我能够解决这个问题，方法是根据结束对间隔进行排序，根据开始对另一个时间进行排序，并取具有匹配开始和结束的间隔的交点。显然有更多优化的解决方案。 这里有一个例子：[1,5][2,10][3,6][2,9]，目标是8。在这种情况下，[2,10]和[2,9]中的任何一个都是正确答案。 我想问题的关
-
假设我有一个这样的范围列表 现在我想找到一个范围，比如。我的算法应该给我这个范围的所有范围。例如，这个的输出应该是 <代码>输出-[1,3]、[2,5]、[4,6]、[8,10] 我该如何着手解决这个问题？ PS：我知道段树可能会有所帮助。我可以在其中构建树来存储间隔并查询位于间隔内的Point，但如何在给定间隔的情况下获取所有间隔。
-
我需要知道不同事件发生的频率。例如，在过去 15 分钟内发生了多少个 HTTP 请求。由于可能有大量的事件（数百万个），因此必须使用有限的内存量。 Java中有什么util类可以做到这一点吗？ 如何在Java中实现这个自我？ 理论用法代码可以如下所示： 编辑：它必须是一个实时值，可以在一分钟内更改数千次，并且将在一分钟内查询数千次。基于数据库或文件的解决方案是不可能的。
-
假设您有一个间隔列表，例如[（0 4），（1 3），（2 5），（2 6）]。此列表未排序。然后给您一个范围，如[1 5]。您必须返回适合范围内的间隔数。在这个问题中，它将返回2。（（1 3）和（2 5）） 间隔列表保持不变，但我们最多得到100000个查询，每个查询由一个范围组成。对于每个范围查询，我们必须返回适合其中的间隔数。 在研究之后，我读到了间隔树。但是，您只能查询与任何给定范围重叠的间