问题标签 [segment-tree]

我正在尝试解决这个问题：

小女孩有一个包含 n 个元素的数组（数组的元素从 1 开始索引）。

此外，还有“q”个查询，每个查询由一对整数li, ri (1 ≤ li ≤ ri ≤ n)定义。您需要为每个查询找到索引从 li 到 ri（含）的数组元素的总和。

小女孩觉得这个问题很无聊。她决定在回复查询之前重新排序数组元素，以使查询回复的总和尽可能大。你的任务是找出这个最大和的值。

输入：

第一行包含两个以空格分隔的整数 n (1 ≤ n ≤ 10^5) 和 q (1 ≤ q ≤ 10^5) — 数组中元素的数量和查询的数量。

下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 10^5) — 数组元素。

以下 q 行中的每一行都包含两个空格分隔的整数li 和 ri (1 ≤ li ≤ ri ≤ n) - 第 i 个查询。

输出：

在一行中打印一个整数——数组元素重新排序后查询回复的最大总和。

我有段树的知识，所以我通过段树应用了惰性传播方法。

我的努力代码：

我的方法很简单，就像使用段树所说的那样，最后打印答案。

我的问题是有没有更简单的算法呢？还是我应该优化我的段树代码？

我正在解决http://www.spoj.com/problems/LIS2/spoj的问题。我尝试了几天，但无法想出一个可以通过的解决方案（时间明智）。然后我用谷歌搜索，发现人们在谈论2D segment tree。我搜索了很多，但找不到下降的解释。这个问题还有其他解决方案吗？？
同样在 topcoder 上，我发现人们说这个问题类似于www.spoj.com/problems/NICEDAY。我很久以前就解决了这个问题，那时我什至不知道1D segment tree。
所以任何人都可以建议一些解决方案，LIS2最好使用2D segment tree.

PS：我不是在寻找代码，请不要发布代码对实现的广泛解释，数据结构的空间/时间复杂度就足够了。

我正在尝试为更新和范围查询创建一个通用的段树类。

我不想假设元素只是整数，并且对一系列元素进行的操作将是它们的总和或乘积，我希望用户提供元素的类型 T 和一个函数，我将其命名为compose。

此函数接受 T 类型的两个参数并返回相同类型 T 的值。此返回值是在 2 个元素的范围内执行所需操作时的结果，我可以使用它在任意范围内执行相同的操作元素的数量。

课程如下：

当我尝试使用这个类时，结果发现没有使用我作为参数接收的compose函数，相反，正在使用类 binary_function_unitype中的函数。

我希望用户的函数定义会覆盖类 binary_function_unitype中的函数定义，我的工作就会完成。但那并没有发生。使用该类的程序如下：

有人可以告诉我我的方法有什么缺陷，或者我是否误解了一些关于在 C++ 中使用继承或模板的基本概念？

谢谢。

段树、区间树、二叉索引树和范围树在以下方面有什么区别：

• 关键思想/定义
• 应用
• 更高维度的性能/订单/空间消耗

请不要只给出定义。

我有一个包含 10 个数字的数组 supprse A[10] = {1,2,3,4,5,6,7,8,9,10} 我必须计算特定范围内的数字相乘但没有得到正确答案，我使用的是段树，不知道如何使用查询操作这是我的代码：

在解决刺伤问题时，在哪里可以找到实现分段树的参考？刺伤问题要求返回包含给定点 q 的所有间隔（从 [a, b], 1 <= a <= b <= n 形式为 [a, b], 1 <= a <= b <= n 的预定义的一组 m 间隔）返回。

极端情况：只有一点 [a, a] 的区间。

到目前为止，我设法获得了以下代码，但它肯定不起作用，我无法真正找到错误：

我编写了用于在数组上触发产品范围查询的代码。

注意：这个问题与Multiplication in a range不重复。我的问题是不同的

我为此编写了代码，

我很确定我选择的 R 没有通过一些测试用例。^{我也用 10 18}尝试了R。但仍然是同样的问题。不知道为什么会这样？

我的问题是，是 RI 选择的问题，还是每个测试用例中通过的不同 M 的问题。

注意：真的不期待解决方案，只是期待线索

问候

我正在尝试确定一种合适的方式来完成以下任务。

我想要范围 - >在特定范围内设置查找（比如[0x0 - 0xffffffff]）。值被插入到范围内（所以如果我们使用 T = 唯一字符串），我可能会 insert("beef3490", [0x1234, 0xFFFF]); 并且单个 id 可能有多个插入，它们可能重叠也可能不重叠。此外，可能会插入其他重叠的值，并且它们重叠的地方我应该收到一组唯一字符串作为结果。最后，值也可以从范围中删除（不一定匹配，但通常包含在它们的初始插入范围内）。

这是一个简化的示例用法：

这给我带来了一些问题：

1. 是否有此类问题的通用名称，或者我可以从中找到见解的类似类型的问题？

2. 考虑到以下限制，理想的实现是什么：

   • 快速/非常快的查找时间
   • 内存使用不会膨胀（即以下操作具有等效的占用空间）
   • • 插入[10,20]，插入[20,30]，删除[14,24]
   • • 插入[10,15]，插入[25,30]
   • 与上一个类似，数据结构在长时间运行的系统上应该具有稳定性
   • 插入/删除时间并不是绝对可怕的（尽管它们不需要像查找一样快）

3. 给定一个理想的实现，您对在 C++ 中使用它有什么建议吗？

感谢所有回复和帮助。

给定二维平面上的 N (N <= 10 ⁶ ) 个点和一个整数 D (N <= 10 ⁶ )，我们想要找到两个点 p1,p2（p1 右侧的 p2），使得p1.y并且p2.y至少为 D 并且p2.x - p1.x被最小化。

x 和 y 轴在 0..10 ^6范围内

这是 USACO 过去比赛中的一个问题。

这是我解决它的尝试：
MAXY = N 个点中的最大 y 轴。
假设我们知道 p1，那么我们可以很容易地找到 p2；通过取所有 y 轴在p1.y+DMAXY 范围内或在 0 到 0 范围内p1.y-D的点，并取最小 x 轴大于 的点p.x。这将是 p2 的最佳选择。

但是由于我们不知道 p1，我们将不得不尝试 p1 的所有点，因此应该有效地找到 p2 的最佳选择。

我为此使用了分段树。树中的每个节点都会按照 x 轴的排序顺序存储相应范围内的所有点。在查询时，如果一个节点落在查询范围内，那么我们对数组进行二进制搜索p1.x并返回大于它的最小元素。

对于 p1 的每一个选择，我们用 0,p1.yD 和 p1.y+D,MAXY 的范围查询树两次，并取两个点中最好的一个。

树的构建可以在 O(NlogN) 时间内完成。每个查询将花费 O(logN*logN) 时间，并且我们进行 N 次查询，因此所花费的总时间为 (Nlogn*logn)，它可能不会在 2 秒的时间限制内运行。(10 ⁶ *20*20)。此外，占用的内存将是 O(NlogN)，大约为 80 mb (100000*20*4 kb)，因为限制为 64 mb，所以太多了。

我们如何才能更快地执行查询并使用更少的空间？

我知道这个问题可以使用修改后的归并排序来解决，我也编写了相同的代码。现在我想使用Segment Tree来解决这个问题。基本上，如果我们从右到左遍历数组，那么我们必须计算“有多少值大于当前值”。Segment Tree怎么实现这个东西呢？

我们必须在Segment Tree Node上存储什么类型的信息？

如果可能，请提供代码。