检查子序列的所有前缀和的动态数据结构>= 0和sum是= 0

Question

让我们考虑元素为 $ - 1,0,1 $ 的序列。
随后 $ a [i ... j] $ 是 $ good $ 如果其元素的总和 $= 0 $ 。
示例：对于序列 $ 1,1,0，-1，-1,1 $ 后续 $ 1,0，-1， -1,1 $ $ good $ 。

后续 $ a [i ... j] $ 是 $ supergood $ 如果它是好的前缀 - sum是 $> $>= 0 $
示例：对于序列 $ 1,1,0，-1，-1,1 $ 后续 $ 1,0，-1， -1,1 $ 不是 $ supergood $ 但 $ 1,0，-1 $ $ supergood $ 。

现在我想拥有动态数据结构，它允许我有效地执行这些操作：

• 插入（s，x，i） - 插入 $ x $ 进入 $ s $ 上< Span Class=“Math-Container”> $ i $ 'th位置
• 删除（s，i） - 删除 $ i $ 'th元素
• Issupergood（S，I，J） - 检查后续 $ i $ ， $ j $ 超级烹饪

解决方案可以是AVL树，左和右子树中的元素和。更新易于更新，允许我们检查<跨度class=“math-container”> $ o（\ log（n））$ ：

1. 查找节点i（假设v） $ \ o（\ log（n））$
2. 查找节点j（假设u） $ \ o（\ log（n））$
3. 检查v.val + v.lsum - u.lsum== 0 $ \ o（1）$

但如果谈到检查超级良好的条件，我看不到如何。

Answer 1

为每个子树增强树存储，为每个子树存储该子树中元素序列的前缀和。然后，您可以在 $ o（\ log n）$ 时间中检查超级良好状态。这是你的运动，所以我会让你锻炼细节。

提示＃1：每个前缀可以分解为 $ o（\ log n）$ 子树的联合。

提示＃2：元素的最小值 $ [x_1，\ dots，x_k] $ 是（a）的最小值元素的前缀和 $ [x_1，\ dots，x_j] $ ，（b），元素之和 $ [x_1，\ dots，x_j] $ 加上元素的最小值 $ [x_ {j + 1}，\ dots，x_k] $ 。现在让 $ [x_1，\ dots，x_j] $ 表示节点左子树中的元素， $ [ x_ {j + 1}，\ dots，x_k] $ 节点中的元素和右子树中的元素，这为您提供了一种方法来重复在节点中的增强值给出它的增强值两个孩子。

---

通常，具有增强的典型策略是您想要选择增强的值，以便（1）您可以有效地更新或重新计算节点中的增强值（通常，在 $ o（1）$ 时间），给定其两个孩子的增强值，（2）您可以有效地回答查询（通常是 $ o（\ log n）$ time），使用增强值。我们通常通过利用以下事实来处理（2），即连续值的每个间隔都可以分解为 $ o（\ log n）$ 子树的脱节联合。