问题标签 [segment-tree]

我对分段树很陌生，想通过在分段树上做更多的练习来让自己忙起来。

这个问题实际上更像ACM，并且有以下条件：有n个数字和m个操作，n，m<=10,000，每个操作可以是以下之一： 1. 更新一个区间减去一个数字x，x可以不同每次 2. 查询一个区间，找出区间中有多少个数 <= 0

在这里构建段树和更新显然可以在 O(nlog n) / O(log n) 中完成，但我不知道如何在 O(log n) 中进行查询，谁能给我一些建议/提示？任何的意见都将会有帮助！谢谢！

TL;博士：

给定 n 个数字和 2 种类型的操作：

1. 将 x 添加到 [a,b] 中的所有元素，x 每次可以不同
2. 查询[a,b]中的元素个数<C，C给定常数

如何使操作 1 和 2 都可以在 O(log n) 中完成？

我在使用延迟传播实现段树时遇到了麻烦。我刚刚阅读了段树并尝试使用它做一个简单的问题（http://www.codechef.com/problems/FLIPCOIN），但我得到了错误的答案。请帮助我实施。这是我的代码（如果您更喜欢 ideone：http ://ideone.com/SHVZ5y ）：

我想从给定的数组中找到最大的和连续子数组。我知道使用 Kadane 算法的动态编程概念找到最大和连续子数组方法的 O(n) 方法。

但是如果范围查询的数量非常大，这将花费很多时间。有没有办法使用 Segment-Trees 来解决它，因为它是回答它在 O(log(n)) 时间内解决的范围查询的最佳选择。谢谢你。

我知道 BIT 是如何工作的。但我想知道是否可以使用 BIT 来查找完整范围内的最小/最大值元素，或者更具体地说，在所有更新过程完成后查找最小值（或最大值）。现在，我知道使用段树可以很好地实现这一点，但是使用 BIT 可以做到这一点吗？

谢谢。

PS：我知道遍历完整BIT并计算每个索引的值的明显方法。我正在寻找一种更有效/优化的方式。

a[]假设我有一个长度为的未排序整数数组N。现在我想找到给定区间a[i]-a[j]( 1 <= i <= j <= N) 内的第 k 个最小整数。例如：我有一个数组a[10]={10,15,3,8,17,11,9,25,38,29}。a[2]-a[7]现在我想找到区间内的第三个最小元素。答案是 9。我知道这可以通过对该区间进行排序来完成。但这需要O(Mlog(M))( M = j - i + 1) 时间。另外，我知道，这可以通过段树来完成，但我不明白如何修改它来处理这样的查询。

给定一个 N*N 矩阵和 Q 查询相同的给定矩阵。每个查询的形式为 x1,y1,x2,y2。我们必须找到由 (x1,y1) 和 (x2,y2) 分别定义为左上角和右下角的子矩阵中不同元素的数量。约束：N<=300 Q<=10^5 我正在使用简单的方法来迭代每个查询的子矩阵。有没有更好的方法？

我阅读了关于 BIT.. topcoder 等的各种教程，所有操作都在其中得到了很好的解释，但是我没有得到 BIT 的创建方式，即

给定一个 1-D 数组，e 如何获得相应的 BIT？前任。如果数组是 10 8 5 9 1 这个 BIT 是什么？

我是初学者，如果我的问题听起来很愚蠢，但我不明白这一点，我深表歉意。所以，请帮忙。

I was trying this problem on spoj. www.spoj.com/problems/RRANGE.It requires segment tree.But the problem is with the size of array.Here (1 <= N <= 1,000,000,000).Any way to work around this problem? Here is my implementation(gives correct answer for nearly N<1000000)

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

桌子上放着 N 个硬币，编号从 0 到 N - 1。最初，每个硬币都是反面朝上的。
您必须执行两种类型的操作：

1. 翻转所有编号介于 A 和 B 之间的硬币。这由命令“0 A B”表示

2. 回答在 A 和 B 之间编号的硬币有多少是正面的。这由命令“1 A B”表示。

输入：第一行包含两个整数，N 和 Q。接下来的 Q 行中的每一行都是上面提到的“0 A B”或“1 A B”的形式。

输出：为“1 A B”形式的每个查询输出 1 行，其中包含相应查询所需的答案。

我使用的是分段树。因此，每次用户输入类型 1 AB 的查询时，输出都是该区间 [A,B] 的总和。但是我收到了一个超出时间限制的错误。我相信错误是由于更新步骤 0 A B 造成的。更新数组中的元素后，我重建了树。代码如下。有人可以帮助我更快地更新吗？

顺便说一句 - 我正在为示例输入获得所需的输出。

编辑：

根据 GeeksForGeeks，树的构建成本为 O(n)，更新方法为 O(log n)。所以这里是更新的新方法：

现在 main 方法中的 if 循环修改为：

但仍然出现 TLE 错误。

我最近阅读了关于线段树中的惰性传播并对其进行了编码。但是当假设我需要除以值而不是添加值（= val）时我被卡住了。怎么做？请帮忙

我的更新功能如下：