问题标签 [segment-tree]

有段树的 STL 吗？

在竞争性编程中，为 seg 树编写代码需要花费大量时间。我想知道是否有任何 STL 可以节省大量时间。

假设您有a1..an数字和一些查询[l, k] (1 < l, k < n)。问题是找到[l, k]两个相等数字之间的区间最小距离。

示例：（间隔 l,k 显示为 |...|）

答案 2 (101)

答案 1 (22)

答案 2 (303) 或 (323)

我考虑过分段树，但是当查询在多个节点之间共享时，很难连接每个树节点的结果。我尝试了一些方法来加入他们，但看起来很难看。有人可以给我一个提示吗？

澄清

感谢您的回答。问题是查询很多，所以o(n)不好。我没有无意中提到分段树。它执行复杂的查找或数组[l, r]查询。我们可以在这里做一些预处理以适应 o(logn) 吗？[l, r]SUM[l, r]MINlog(n)

我得到了不正确的问题可怕的结果

这是我的代码：http: //ideone.com/1Yb3yp

我正在考虑这个问题，并且在尝试执行此操作时遇到了很多错误。可能吗？

在范围更新问题中，我想为范围内的数组元素添加一个值。可以假设数组（或某些数据结构）已排序。

一个简单的算法是循环从起始元素到结束元素，并为每个元素添加一个值 v。

但是在最坏的情况下，当范围是从第一个元素到最后一个元素时，这需要 O(n) 时间。有没有更快的方法来做到这一点？我应该使用段树来做吗？

给定一个未排序的 n 个整数数组，我知道我可以按照以下方法在 O(N lg N) 中使用 BIT 找到反转的总数：Count Inversion by BIT

但是，如果我必须查询 O(lg N) 中的总反转数的任意范围，是否有可能？

AO(N lg N) 预计算是可以接受的。

我做了一些研究，似乎 N 因素是不可避免的......任何建议将不胜感激！

我在理解段树复杂性方面遇到问题。很明显，如果你有一个只需要改变一个节点的更新函数，它的复杂度将是 log(n)。但是我不知道为什么查询（a，b）的复杂性是log（n），其中（a，b）是需要检查的间隔。谁能为我提供直观/正式的证据来理解这一点？

已经给出了一个最初具有一些 Max.val 值的数组，然后有查询在 Range L,R 中进行更新，使得任何位置的值都是最小值。例如：

在上述查询之后，我必须显示我的最终结果array:i.e 2 1 1 1 Max.val

我正在使用Segment Tree来解决这个问题，但我得到了 TLE(Time limit Exceeded)。我不知道为什么？我的方法是logN。 这是我的更新功能

约束：

我做错了什么或有更好的方法吗？调用一个函数：

给定一个长度为 N 的一维整数数组 A。我们需要 Q 次查询以下类型中的每一种：

注意：M 固定为 10^9 + 7

查询 1 : 1 xyv ：这意味着将 v 添加到 1 个基本索引数组中从 x 到 y 的所有元素，然后将它们取模 M。

查询 2 : 2 xyv：这意味着将 v 与 1 个基本索引数组中从 x 到 y 的所有元素相乘，然后将它们取模 M。

查询 3 : 3 xyv ：这意味着将 v 替换为 1 个基本索引数组中从 x 到 y 的所有元素。

查询 4 ​​: 4 xy ：这是一个报表查询，需要找到 A 中从 x 到 y 的值的总和，即

现在如何处理这些查询？如果它是带有段树的加法和求和查询，我知道要处理查询。但是不知道这个。请帮我解决这个问题。

约束：1 ≤ N,Q ≤ 10^5 和 1 ≤ A[i],v 的初始值 ≤ 10^9

我有很多查询的问题，有四种类型：

1. 添加到范围。

2. 初始化一个范围。

3. 将范围与标量相乘。

4. 在一个范围内查找运行总和。

由于查询数量庞大，我必须使用带有延迟传播的分段树，但我一直坚持如何在超过 2 种类型的查询上使用延迟传播。我如何能够确定稍后要进行更新时，要进行哪种类型的更新（即加法、乘法、初始化）？