From 90d786362ee9719645bc3d60b00b405569cab401 Mon Sep 17 00:00:00 2001 From: Sshwy Date: Mon, 19 Aug 2019 21:53:26 +0800 Subject: [PATCH] Update docs/ds/sqrt-tree.md Co-Authored-By: Margatroid --- docs/ds/sqrt-tree.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/ds/sqrt-tree.md b/docs/ds/sqrt-tree.md index b3c07691..1e5086be 100644 --- a/docs/ds/sqrt-tree.md +++ b/docs/ds/sqrt-tree.md @@ -1,4 +1,4 @@ -给你一个长度为 n 的序列 $\left\langle a_i\right\rangle_{i=1}^n$ ，再给你一个满足结合律的运算 $\circ$ （比如 $\gcd,\min,\max,+,\operatorname{and},\operatorname{or},\operatorname{xor}$ 满足结合律），然后对于若干次区间询问 $[l,r]$ ，我们需要计算 $a_l\circ a_{l+1}\circ\dotsb\circ a_{r}$ 。 +给你一个长度为 n 的序列 $\left\langle a_i\right\rangle_{i=1}^n$ ，再给你一个满足结合律的运算 $\circ$ （比如 $\gcd,\min,\max,+,\operatorname{and},\operatorname{or},\operatorname{xor}$ 均满足结合律），然后对于每一次区间询问 $[l,r]$ ，我们需要计算 $a_l\circ a_{l+1}\circ\dotsb\circ a_{r}$ 。 Sqrt Tree 可以在 $O(n\log_2\log_2n)$ 的时间内预处理，并在 $O(1)$ 的时间内回答询问。 -- 2.11.0