标签: segment-tree

我知道这个问题可以使用修改后的合并排序来解决,我编码相同.现在我想使用Segment Tree解决这个问题.基本上,如果我们从右到左遍历数组,那么我们必须计算"有多少值大于当前值 ".Segment Tree如何实现这一目标？

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

如果可能请提供代码.

我们怎样才能证明update和query操作上段树(http://letuskode.blogspot.in/2013/01/segtrees.html)(不要与间隔树混淆)是O(log n)？

我想到了一种这样的方式 - 在每个节点,我们在左右子树上最多进行两次递归调用.如果我们能够证明其中一个呼叫相当快地终止,那么时间复杂度将以对数为界.但是我们如何证明这一点呢？

给定n个整数的未排序数组,我知道我可以在这个方法之后找到使用BIT在O(N lg N)中的反转总数:BIT计数反转

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

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

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

我正在学习段树,我遇到了这个问题.有阵列A和2类型的操作

1. Find the Sum in Range L to R 
2. Update the Element in Range L to R by Value X.

更新应该是这样的

A[L] = 1*X;
A[L+1] = 2*X;
A[L+2] = 3*X;
A[R] = (R-L+1)*X;

我应该如何处理第二类查询,任何人都可以通过分段树给出一些算法来修改,或者有一个更好的解决方案

我一直在考虑以下问题:

我们给出了一组n个数字.我们从第一个索引开始,我们的任务是到达最后一个索引.每一步我们都可以向前跳一两步,而我们跳转到的索引数就代表了我们为访问该指数需要支付的费用.我们需要找到最便宜的方式来到阵列的末尾.

例如,如果数组看起来像这样:[2,1,4,2,5]最便宜的方式是10:我们访问索引1-> 2-> 4-> 5我们必须支付2 + 1 + 2 + 5 = 10这是最便宜的方式.设f(i)是到达指数i的最便宜的价格.通过实现f(i)= arr [i] + min(f(i-1),f(i-2)),我们可以在O(n)时间内通过动态编程 轻松计算

但是这里有一个转折点:数组会多次更新,每次更新后我们都需要能够在O(logn)时间告诉我目前最便宜的方式.通过告知将要更改的索引以及将更改为的数字来更新数组.例如,更新可能是arr [2] = 7将我们的示例数组更改为[2,7,4,2,5].现在最便宜的方式是11.

现在我们如何在O(logn)时间内支持这些更新？有任何想法吗？

这是我到目前为止所提出的:首先,我将为之前描述的动态编程创建一个数组f.我将以下列方式将该数组的内容存储在段树s中:s(i)= f(i)-f(i-1).这将使我更新的间隔˚F中(加上一个常数,以每一个值)O(LOGN)时间,在给定的索引处索要值O(LOGN)的时间.这会很方便,因为在经过一些更新之后,经常发生f中的所有值需要在f中的某个给定索引之后增加一个常量.因此,通过在每次更新后询问段树中的s(n)的值,我们将得到我们需要的答案.

然而,更新后可能会发生不同的事情:

1. f中只需要更新一个值.对于exampe如果[2,1,4,2,5,4,9,3,7]被改变为[2,1,9,2,5,4,9,3,7]仅F(3)将需要更新,因为无论如何没有最便宜的方式通过3.索引.
2. 给定索引后的f中的所有值都需要通过常量更新.这就是分段树的优点所在. …

我没有场景，但问题就在这里。这简直让我发疯。有一个 nxn 布尔矩阵，最初所有元素均为 0，n <= 10^6 并作为输入给出。接下来将有最多 10^5 个查询。每个查询可以将 c 列的所有元素设置为 0 或 1，或者将 r 行的所有元素设置为 0 或 1。还可以有另一种类型的查询，打印 c 列或 r 行中 1 的总数。

我不知道如何解决这个问题，任何帮助将不胜感激。显然每个查询的 O(n) 解决方案是不可行的。

我见过许多使用 O(4*N) 内存的线段树实现。无论如何，线段树是否可以使用 2*N-1 内存？我找不到任何执行此操作的实现。即使他们谈论的空间复杂度实际上是 2*N-1，他们仍然分配 4*N。

编辑：我的意思是，对于 n 个数字的数组，您可以使用 2n-1 个数字的数组作为线段树。每个实现都使用 2*（大于 n 的 2 的下一个幂）的数组。

我知道 O 表示法省略了常数，但对于非常大的 n 来说，它是 2*N-1 还是 4*N 很重要，这就是我问这个问题的原因。

我在 HackerEarth上的这篇文章中发现，可以通过使用数组来实现段树，其中位于数组索引n的节点的子元素位于索引2n和2n+1 处。

它还指出，为了在我的段树中存储n 个元素，我需要2n+1 个节点。

然而，最近当我解决了一些与段树相关的问题时，有时我的代码会出现运行时错误，当我将用于存储段树的数组大小更改为4 x (要存储在段树中的数组大小) 时，该错误得到了解决。我如何确定段树实际上需要 n 个元素的 4n 大小的数组。

给定一个数组 n 个元素 (n <= 10^5) 计算范围的数量 [L; R] (L <= R) 最大值与最小值之差为偶数。

例如，n = 5
a[] = {4, 5, 2, 6, 3}
答案是 11：[1;1], [1;4], [1;5], [2;2], [2;4]、[2;5]、[3;3]、[3;4]、[3;5]、[4;4]、[5;5] 时间限制为 1 秒

如果 n <= 1000，O(n^2) 的 natvie 算法就可以了。我认为我们可以通过使用堆栈或双端队列来改进这种方法。但这太难了。

有什么有效的办法吗？

所以这是一个问题，我给了一个整数数组，它的数字都是不同的，假设它是

int[] data = {21, 34, 12, 88, 54, 73};

现在我想看看子数组或范围是否包含一个范围内的数字（也给出了）。换句话说，我想查看数组的某个范围是否包含某个范围内的数字。例如，如果我有一个函数，check(int a, int b, int l, int r)其中a和b是数组的范围，l并且r是数字的范围。

因此，对于上面的数组，check(0, 2, 20, 50)应该返回true，因为 from index = 0 to 2，有21, 34, 12，并且有两个数字 ，21, 34在 的范围内20 to 50。

所以另一个例子是应该check(2, 3, 20, 80)返回，false因为 ,12, 88没有 20, 80 范围内的数字。

我正在考虑使用线段树，因为据我所知，RMQ（范围最小查询）可以通过使用线段树来解决，因此我认为线段树也可以解决这个问题；"get" function然而，线段树的全部都是"single"（也许不是最好的词），所以，我想知道线段树应该保存哪些节点。是否有任何算法可以回答每个查询，而O(log(n))不是"build" …