From 591a1f0be59662f673cbf3258f11407ad011a215 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 8 Sep 2019 20:28:41 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/ds/sparse-table.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/docs/ds/sparse-table.md b/docs/ds/sparse-table.md index 823abce5..d5cfe6fd 100644 --- a/docs/ds/sparse-table.md +++ b/docs/ds/sparse-table.md @@ -16,7 +16,7 @@ RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最 ## ST 表 - ST 表基于倍增思想,可以做到 $O(n\log n)$ 预处理, $O(1)$ 回答每个询问。但是不支持修改操作。 +ST 表基于倍增思想,可以做到 $O(n\log n)$ 预处理, $O(1)$ 回答每个询问。但是不支持修改操作。 暴力跑的慢的原因在于检索了每一个点。 @@ -26,7 +26,7 @@ RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最 显然, $f[i,0]=a[i]$ -根据定义式,写出状态转移方程: $f[i,j]=\max(f[i,j-1],f[i+2^{j-1},j-1])$ +根据定义式,写出状态转移方程: $f[i,j]=\max(f[i,j-1],f[i+2^{j-1},j-1])$ 我们可以这么理解:将区间 $[i,i+2^j-1]$ 分成相同的两部分 @@ -107,7 +107,7 @@ $$ ## 总结 - ST 表能较好的维护区间信息,时间复杂度较低,代码量相对其他算法不大。但是, ST 表能维护的信息非常有限,不能较好地扩展,并且不支持修改操作。 +ST 表能较好的维护区间信息,时间复杂度较低,代码量相对其他算法不大。但是,ST 表能维护的信息非常有限,不能较好地扩展,并且不支持修改操作。 ## 练习 -- 2.11.0