问题标签 [segment-tree]

我必须使用段树（如果可能，可能是其他数据结构）来计算一个区间内的最小值，更具体地说，在 [1,i] 上，其中 1 是数组的第一个元素。现在，我有一些查询要更新具有不同值的区间（即从 [1,i-1] 开始），更具体地说，我必须将 (2i-3) 添加到第一个元素，将 (2i-5) 添加到第二个元素，依此类推直到 (我必须添加 (2i-(2(i-1)+1) 即 1 的第 i-1) 个元素。进行此更新后，我必须从 [1,i] 计算最小值。必须这样做对于 1<=i<=N 和 N 的顺序是 10^5。所以你会做一些 O(NlogN) 的事情来让它运行。

给定墙的水平截面，以及从坐标 Xi 到 Yi 应用的 N 层油漆，输出可见的不同层数。

这是问题链接http://www.spoj.com/problems/POSTERS/

这是我的解决方案http://ideone.com/gBJKnL

方法：我尝试通过 Segment Tree 懒惰地更新子节点值来解决问题，最近的值在他们的懒惰更新中替换了旧的值。这样，只有最近的油漆被应用到水平横截面。尽管代码在自定义测试用例上运行良好，但它会占用大量内存并被在线法官中止。

我想用段树来解决 Joseph Flavius 问题。我几乎可以肯定，简单的模拟（即行列表）是O(n^2). 我想要实现的是在特定距离的数组上跳跃，取自段树。换句话说，段树将保留有关已删除元素数量的信息，并从树中获取一些信息将允许在 O(1) 中找到下一个要删除的元素。问题是我不知道如何在段树中存储信息以使其适用于 Joseph Flavius 问题。

每个节点中保留了某种额外的值？但是如何查询下一个元素呢？

给定 300000 个段。考虑任何一对段：a = [l1,r1]和b = [l2,r2]。如果l2 >= l1和r2 <= r1，它是“好”对。如果a == b，则为“坏”对。过分来说，这是“坏”的一对。

如何使用段树和扫描线查找给定段中所有“好”对的数量？

我需要基于段树的数据结构，但与经典段树有一个区别。DS 应该支持元素的轻松移动。我的意思是我想要 ds 我可以：

• l对段进行查询（即从 index到 index的元素总和r）
• 在任何索引之前插入新元素，然后移动新元素右侧的所有元素

如果所有这些操作都可以在O(logn) Greetings中工作，那就太好了

我正在尝试构建一个段树，但节点结构不清楚，有人可以解释一下我找到的代码吗

我有一个问题，需要一个可以处理 2 个操作的结构：

1. 将节点的值从位置 x 更改为位置 y 到 newValue。

2. 获取从位置 a 到 b 的值的总和。

节点数为 50000，查询数为 50000。我试图用延迟更新实现 IT 树，但我不知道如何。第一个操作与通常的加法和乘法操作有些不同。

有没有办法使用分段树结构来计算数组中给定值的频率？

假设有一个大小为 N 的数组 A，并且数组的每个元素 A[i] 都包含值 0、1 或 2。我想执行以下操作：

• 计算数组的任何范围 [a,b] 中的零数量
• 递增（mod 3）数组的任何范围 [a,b] 中的每个元素

示例：如果 A = [0,1,0,2,0]：

• Query[2,4] 必须返回 1 ，因为 [2,4] 范围内有一个 0
• Increment[2,4] 将 A 更新为 [0,2,1,0,0]

这看起来与 Range Sum Query 问题非常相似，可以使用 Segment Trees 来解决（在这种情况下，由于范围更新，使用 Lazy Propagation），但是我没有成功地将我的 seg 树代码调整到这个问题，因为如果我存储树中的值就像在正常的 RSQ 中一样，任何包含值“3”（例如）的父节点都没有任何意义，因为有了这些信息，我无法提取该范围内存在多少零。

提前致谢！

--

编辑：

段树是在其节点中存储与数组相关的区间的二叉树结构。叶节点存储实际的数组单元，每个父节点存储其子节点的函数 f(node->left, node->right)。段树通常用于执行范围求和查询，其中我们想要计算数组范围 [a,b] 中所有元素的总和。在这种情况下，父节点计算的函数是其子节点中值的总和。我们想使用 segtrees 来解决 Range Sum Query 问题，因为它允许在 O(log n) 内解决它（我们只需要下降树，直到找到完全被我们的范围查询覆盖的节点），比朴素的 O(n) 算法。

考虑一个数组（基于 0 的索引）我必须找到所有可能 range[i,n] 的不同元素的总和，其中 0< i < n

例子：

O(n^2) 解决方案是一种可能的解决方案，虽然我找不到好的教程，但我已经阅读了持久段树也可以做到这一点。

它可以在少于 O(N^2) 的时间内解决吗？

如果有人指向持久段树，请解释或提供一些好的链接？

给定一个初始化为 0 的数组 arr，即 arr[i]=0 其中 0 < i < n

对其进行了两次操作

1. 更新 krx

   更新执行以下操作：

   /li>

2. 查询 kr

   查询计算以下总和：

   /li>

我的解决方案：
我想到了蛮力，但它很慢。我想到了段树，但是在段树中，更新是按常数执行的，所以它失败了。什么可能是解决这个问题的好算法？

约束

数组的大小是 <=10^5

操作数（更新，查询）<=10^5