From fca99f60e2e26ba48318bf8c579d5ccec2fb2543 Mon Sep 17 00:00:00 2001 From: Shuhao Zhang <594422141@qq.com> Date: Tue, 20 Aug 2019 20:28:05 +0800 Subject: [PATCH] =?utf8?q?=E7=94=A8=E6=B3=A8=E8=A7=A3=E6=A0=BC=E5=BC=8F?= =?utf8?q?=E6=98=BE=E7=A4=BA=E6=8F=90=E7=A4=BA=E5=86=85=E5=AE=B9?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/topic/rmq.md | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/docs/topic/rmq.md b/docs/topic/rmq.md index 824e75cd..5d7c8702 100644 --- a/docs/topic/rmq.md +++ b/docs/topic/rmq.md @@ -44,10 +44,12 @@ Four russian 是一个由四位俄罗斯籍的计算机科学家提出来的基 当然询问由于要跑三个 ST 表,该实现方法的时间复杂度较大。 -> 一些小小的算法改进 -> 我们发现,在询问的两个端点在数组 A 中属于不同的块的时候,数组 A 中块内的询问是关于每一块前缀或者后缀的询问。 -> 显然这些询问可以通过预处理答案在 $O(n)$ 的时间复杂度内被解决。 -> 这样子我们只需要在询问的时候进行至多一次 ST 表上的查询操作了。 +!!! note "一些小小的算法改进" + 我们发现,在询问的两个端点在数组 A 中属于不同的块的时候,数组 A 中块内的询问是关于每一块前缀或者后缀的询问。 + + 显然这些询问可以通过预处理答案在 $O(n)$ 的时间复杂度内被解决。 + + 这样子我们只需要在询问的时候进行至多一次 ST 表上的查询操作了。 ## 笛卡尔树以及其构造 -- 2.11.0