From d38ea73ee279659188764baef0108b2738c1578d Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 25 Aug 2019 06:12:23 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/ds/sqrt-tree.md | 10 +++++++--- docs/misc/complexity.md | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-) diff --git a/docs/ds/sqrt-tree.md b/docs/ds/sqrt-tree.md index 8fb8bcac..acde1df2 100644 --- a/docs/ds/sqrt-tree.md +++ b/docs/ds/sqrt-tree.md @@ -110,13 +110,17 @@ Sqrt Tree 也支持区间覆盖操作 $\operatorname{Update}(l,r,x)$ ,即把 在第一种实现中,我们只会给第 $1$ 层的结点(结点区间长度为 $O(\sqrt{n})$ )打懒标记,在下传标记的时侯直接更新整个子树,复杂度为 $O(\sqrt{n}\log\log n)$ 。操作过程如下: 1. 考虑第 $1$ 层上的结点,对于那些被修改区间完全包含的结点,给他们打一个懒标记; + 2. 有两个块只有部分区间被覆盖,我们直接在 $O(\sqrt{n}\log\log n)$ 的时间内 **重建** 这两个块。如果它本身带有之前修改的懒标记,就在重建的时侯顺便下传标记; + 3. 更新根结点的 $\left\langle P_i\right\rangle$ 和 $\left\langle S_i\right\rangle$ ,时间复杂度 $O(\sqrt{n})$ ; + 4. 重建 $index$ 树,时间复杂度 $O(\sqrt{n}\log\log n)$ 。 -现在我们可以高效完成区间修改了。那么如何利用懒标记回答询问?操作如下: + 现在我们可以高效完成区间修改了。那么如何利用懒标记回答询问?操作如下: + +5. 如果我们的询问被包含在一个有懒标记的块内,可以利用懒标记计算答案; -1. 如果我们的询问被包含在一个有懒标记的块内,可以利用懒标记计算答案; -2. 如果我们的询问包含多个块,那么我们只需要关心最左边和最右边不完整块的答案。中间的块的答案可以在 $index$ 树中查询(因为 $index$ 树在每次修改完后会重建),复杂度是 $O(1)$ 。 +6. 如果我们的询问包含多个块,那么我们只需要关心最左边和最右边不完整块的答案。中间的块的答案可以在 $index$ 树中查询(因为 $index$ 树在每次修改完后会重建),复杂度是 $O(1)$ 。 因此询问的复杂度仍为 $O(1)$ 。 diff --git a/docs/misc/complexity.md b/docs/misc/complexity.md index 7dd8f748..1c7682a8 100644 --- a/docs/misc/complexity.md +++ b/docs/misc/complexity.md @@ -28,7 +28,7 @@ author: linehk - $f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n)))$ - $f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))$ -- $\forall a \neq 1, \log_a{n} = O(\log_2 n)$ 。由换底公式可以得知,任何对数函数无论底数为何,都具有相同的增长率,因此渐进时间复杂度中对数的底数一般省略不写。 +- $\forall a \neq 1, \log_a{n} = O(\log_2 n)$ 。由换底公式可以得知,任何对数函数无论底数为何,都具有相同的增长率,因此渐进时间复杂度中对数的底数一般省略不写。 ## 主定理 (Master Theorem) -- 2.11.0