问题标签 [segment-tree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
java - 段树java实现
您知道Java中（二进制）段树的良好实现吗？
c++ - 延迟传播的分段树时间限制问题
以下是http://www.spoj.pl/problems/LITE/使用 Segment Tree 和惰性传播的实现。我是分割树的新手，我不明白为什么我会得到 TLE。有人可以看看它并帮助我纠正我的错误吗？
ruby - 范围/段树 Ruby
我正在寻找 Ruby 中的范围或段树实现。我找不到任何可用的样品或宝石。
有人有示例代码吗？
谢谢，
algorithm - 线段树中的延迟传播？
好吧，我试图在 Codechef 上解决这个翻转硬币的问题。正在用段树解决它。但获得时间限制超过。我搜索了一下，发现必须使用惰性传播。但我无法理解。我的更新功能递归工作（从上到下）。请给出一些提示或举例说明。还要指出我必须更改代码的地方。
在掷硬币时，如果节点值为 1，则在更新期间将其更改为 0，如果为 0，则将其更改为 1。
start 和 end 是原始数组的限制。tree 是段树数组。
algorithm - 段树中的数据映射和延迟传播
看起来整个互联网上只有一篇关于 Segment Tree 中延迟传播的好文章，它是： http ://www.spoj.pl/forum/viewtopic.php?f=27&t=8296
我理解仅更新查询节点并标记其子节点的概念。但是我的问题是，如果我先查询子节点然后再查询父节点怎么办。
在这棵树中（连同堆数组中的位置）
第一个查询，如果我更新[0 4]，它的数据将被改变，它的孩子将被标记。第二个查询，是段[0 9]的读取状态。
在这里，我面临这个问题。我的段树实现是这样的，每个节点的值是其左右子节点的总和。因此，当我更新节点的值时，我必须更新它的所有父节点。为了解决逻辑问题，现在我正在更新节点的所有父节点（直到它到达树的根）。但这会对性能造成影响，我使用分段树进行快速批量更新的整个目的都被扼杀了。
谁能解释一下，我在使用分段树时哪里出错了？
algorithm - 分段树第 K 个最大值
嗨，我正在解决段树的问题，但是我无法对段树的查询功能进行一点修改。
实际上我想要的是我的查询函数应该返回索引 Qa 和 Qb 之间的 (int)(TotalArrayLength/3) th 最大元素。
我编写的查询函数返回 index[1-based] a_begin 和 a_end 之间的最大元素。
但我想返回 index[1-based] a_begin 和 a_end 之间的 (int)(TotalArrayLength/3)th 最大元素。
注意进行查询，我将查询函数称为查询（1,0，N-1，QA，QB）。
我还实现了以下伪代码来编写上面的查询函数，
那么我应该如何修改以在 index[1-based] a_begin 和 a_end 之间找到 (int)(TotalArrayLength/3)th 最大元素。
基本上，我要解决的问题是：
最初，数组包含 0 个或更多元素。随机一些数据将被插入到数组的末尾，并且在任何时候都要做一个查询，返回 TotalArraySize/3 th Max Elements in Array build 到目前为止。
另外，我是否为此目的选择了正确的数据结构。
非常感谢。
c++ - 如何在保持最大值和最小值的同时更新段树中的范围？
我正在从一组数据中实现分段树，并且我还想在更新一系列数据时保持树的最大/最小值。这是我遵循本教程http://p--np.blogspot.com/2011/07/segment-tree.html的初步方法。不幸的是，它根本不起作用，逻辑对我来说很有意义，但我对band有点困惑e，我想知道这是data数组的范围吗？还是树的实际范围？据我了解，max_segment_tree[1]应该保持max范围的[1, MAX_RANGE]，而min_segment_tree[1]应该保持min范围的[1, MAX_RANGE]。
编辑 添加测试用例：
c++ - SPOJ GSS1 WA - 段树
我正在尝试使用段树解决 SPOJ 问题GSS1（你能回答这些查询吗）。我正在使用“init”方法来初始化树，并使用“query”方法来获取范围 [i,j] 中的最大值。
限制 |A[i]| <= 15707 和 1<=N（元素数）<=50000。
程序给出了错误的答案。我调试了大多数情况下的代码（负数、奇数/偶数 N），但我无法弄清楚算法有什么问题。
如果有人能指出我正确的方向，我将不胜感激。
谢谢
c++ - 如何使用延迟传播实现段树？
我正在实现一个段树，以便能够快速回答数组 A 中的以下查询：
- 查询 i, j：范围 (i,j) 中所有元素的总和
- 更新 i, j, k：将 k 添加到 range(i,j) 中的所有元素
这是我的实现：
查询函数非常快，其复杂度为 O(lg N)，其中 N 为 ji。更新函数在一般情况下也很快，但是当ji很大时，更新的复杂度是O(N lg N)，一点也不快。
我搜索了一下主题，发现如果我用惰性传播实现段树，查询和更新的复杂度都是 O(lg N)，渐近地比 O(N lg N) 快。
我还找到了另一个问题的链接，它有一个非常好的段树实现，它使用指针：如何使用延迟传播实现段树？. 所以，这是我的问题：有没有更简单的方法来实现惰性传播，不使用指针，但使用数组索引，并且没有segment_tree数据结构？