问题标签 [range-query]

我想知道是否有人可以确认我构建的查询是否正确。

我有一个嵌套在用户中的User映射，我正在寻找在某个日期之前购买了特定项目的用户。Transaction此外，在Transaction我也有line_items这也是一个嵌套字段。

最初，我构建了以下查询，并根据返回的数据得出结论，该查询可能不正确。

然后我更新了我的查询，现在根据返回的结果我认为查询是正确的。但是，为了避免确认偏差，我想知道是否有人可以解释为什么第二个查询是正确的（假设它是正确的）。

我面临一个问题，我需要找到一个特定的成对总和，其中索引中的第一个元素具有 index > i。

例子：

[1, 2, 3, 4, 6]（索引0到4）

目标总和 = 9

现在，从这个数组中，我需要找到索引中第一个元素具有索引 > 的成对总和i。

现在，显而易见的解决方案是：

1. 计算成对和数组。 [1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6][ O(n^2) ]
2. 循环遍历索引i+1以n找到 target_sum。[ O(n^2) ] (n 是原始数组的长度)

现在，主要问题是2。即使我不能改进（1），我也需要改进（2），因为这会被很多人质疑。

我想到的一种方法：

1. 从成对和数组中创建一个索引数组，值对。O(n^2) [n 是原始长度]
2. 首先使用值对数组进行排序，然后使用索引对数组进行排序。O(n^2 * logn)
3. 对于每个查询，运行二进制搜索以查找值存在的区间。O（登录）
4. 在该间隔上运行另一个二进制搜索以找到索引 > i。

有什么优雅更好的方法吗？

我正在尝试解决 cses 工资查询（https://cses.fi/problemset/task/1144/）

问题：我将制作一个工资频率数组，我将使用坐标压缩，但是在更新时我必须重建坐标压缩并且会出现一团糟。

如何解决这类问题？我在stackoverflow中看到了一个博客，但我无法实现隐式段树的解决方案。

这是我对数组上函数 f() 范围查询的最佳数据结构的理解：

我的问题：

1. 这个对吗？
2. 我是否遗漏了一个重要的数据结构？
3. 如果我想要支持项目插入和删除怎么办？

如果您有任何指示，请提前感谢！