问题标签 [segment-tree]

在一个整数数组（大小 10^5）中，操作是这样的......

1. 对从索引 L 到 R 的每个元素按特定数字 X 进行按位异或运算
2. 求从索引 L 到 R 的数字之和。

我如何使用分段树和惰性传播来做到这一点？

我用这样的功能更新段树。分析说这是瓶颈：

虽然内存操作很快，但我想知道它是否是由递归开销引起的，而它的深度通常不会超过 20。

我从原始分析器中得到的是：

• 4.39434ms - 对数据进行单次二进制搜索的平均时间
• 2642.94ms - 一次更新的时间
• 19.9097ms - 单个 RMQ 查询的时间。

所以.. 一次更新所花费的时间是戏剧性的:)。

答案：找到了一个隐藏的 std::find over map。

我对这个结构如何工作以及如何更新它有一个很好的想法，但是当涉及到延迟传播时我不知道该怎么做，因为很多很多问题都需要在比赛中通过我想知道如何让它工作。

我在 spoj 上尝试这个问题：http ://www.spoj.com/problems/CDC12_H/

如果有人可以向我解释惰性传播如何适应这种情况，我会接受并研究这个想法，我真的不想发布我的代码，因为我的想法是让我自己完成这项工作，但是帮助不大。

我希望有人能解决我的问题。

我目前正在解决段树上的问题。我认为这个问题需要惰性传播概念来解决。由于我对这个概念很陌生，所以我的代码有问题。

简而言之，问题如下：

最初，所有数组元素都是 0，它们的索引为 0 到 N-1

命令 1. 0 xyv - 将 x 和 y 之间的每个数组索引的值更新为 v

命令 2. 1 xy - 输出数组索引 x 和 y 之间所有数字的总和。

输入以整数 T (≤ 5) 开头，表示测试用例的数量。

每个案例包含两个整数 n (1 ≤ n ≤ 105) 和 q (1 ≤ q ≤ 50000)。接下来 q 行中的每一行都包含以下形式之一的任务：

0 xyv (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)

1 xy (0 ≤ x ≤ y < n) 对于每个案例，首先打印案例编号。然后对于每个查询“1 x y”，打印 x 和 y 之间所有数组元素的总和。这是我的尝试：

我想知道为解决范围最小查询问题而制作的段树中有多少个节点。

另外，构建操作需要多长时间，为什么？

该问题的链接是UVA-1394: And There Was One。
朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素，并在最后一次停止：这需要 O(n^2) 时间。
我已经搜索了一种替代算法，并遇到了一个中文博客，该博客指出我使用惰性传播作为 O(N lgN) 时间的解决方案来分割树。
研究了段树后，我尝试为 O(N lgN) 时间形成算法，但无济于事。

---

我的问题是：
1. 可以使用分段树来获得所需的运行时间吗？
2. 如果是，请告诉我如何使用它们。
3. 段树和“zkw”段树是一回事吗？- 他在博客中提到了 zkw 段树。
更新：上述问题是约瑟夫斯问题的一个例子。

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

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

我想在下面的链接中将一个函数添加到延迟传播实现中，将范围设置为 0。目前有一个 update_tree 函数可以增加一个范围，但我不知道如何修改它以便它将在 O(log(N)) 时间内将范围懒惰地设置为零。

http://se7so.blogspot.com.au/2012/12/segment-trees-and-lazy-propagation.html

我正在考虑在每个节点上使用“延迟清除”标志，但我怎么知道先清除然后延迟添加或延迟添加然后清除（这会很清楚）？

我正在尝试在 python 中实现一个段树类。段树允许在对数时间内查询范围（更多关于段树）。在我的实现中，我持有必要的信息，以便能够回答 range 中元素的总和(i, j)。下面是我的代码。由于我是 python 新手，我仍然在每行末尾使用分号（继承自 C++）。

构建函数应该从输入数组构建段树a。当我运行程序时，我得到以下输出：

我不明白为什么序列的所有值都24在build函数退出之后。build调试信息在函数运行时显示了许多其他值，但在它退出后，所有值都神奇地变成了24. 为什么会这样？提前致谢。

我正在尝试实现段树以从数组中的给定间隔中提取最小值。[参考 - http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ ]

以下是相同的代码。

如果我正在构建一int棵树（即使用整数数组存储段树的节点），一切正常。但是一旦我将类型更改为float，就会发生一些恶作剧，表示段树的数组的索引 0-7 和索引 11nan显示了值；int而在树的情况下不会发生这种情况。该函数printSegmentTreeArray()用于打印存储在表示树的数组的每个位置的值。

笔记：-

1.在代码中，正确更改树的数据类型所需的更改由int要替换的前面的float注释块指示。/* $$$ float $$$ */int

2.我确实编写了从查询间隔中提取 Min 的函数，但由于该constructST()函数的行为很奇怪，所以将其删除。

3.我已经针对这两种情况使用以下输入测试了我的代码。

有人可以指出原因吗？