From bc266f01b4971d34e8e16dbe83a5853094cf0856 Mon Sep 17 00:00:00 2001 From: Xeonacid Date: Wed, 10 Oct 2018 20:14:22 +0800 Subject: [PATCH] fix style --- docs/ds/segment.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/ds/segment.md b/docs/ds/segment.md index dad15112..1224a9b6 100644 --- a/docs/ds/segment.md +++ b/docs/ds/segment.md @@ -76,7 +76,7 @@ void build(int s,int t,int p) 上面那短短 $7$ 行代码就能建立一个线段树。 -关于线段树的空间，如果采用堆式存储 (上面的代码就是堆式存储，即$2\times p$是 p 的左儿子,$2 \times p+1$是 p 的右儿子)，d 数组的大小需要是 $n$ (元素个数) 上取到一个 $2$ 的整数次幂再乘以$2$(上界是$4$倍，可利用上述代码自行验证)，如果采用动态开点，则需要两倍的空间 (需要额外地记录左儿子和右儿子的编号 / 地址) +关于线段树的空间，如果采用堆式存储（上面的代码就是堆式存储，即 $2\times p$ 是 p 的左儿子,$2 \times p+1$ 是 p 的右儿子），d 数组的大小需要是 $n$ （元素个数）上取到一个 $2$ 的整数次幂再乘以 $2$（上界是 $4$ 倍，可利用上述代码自行验证），如果采用动态开点，则需要两倍的空间（需要额外地记录左儿子和右儿子的编号 / 地址）。 ### (2) 线段树的区间查询 @@ -267,7 +267,7 @@ int getsum(int l,int r,int s,int t,int p) 这里我总结几个线段树的优化： -- $a\times 2$ 可以用 $a<<1$ 代替，$a\div 2$ 可以用 $a>>1$ 代替（$<<1$和 $\times 2$ 的速度是一样的，即使不开 O2，但$>>1$速度比$\div 2$快）。 +- $a\times 2$ 可以用 $a<<1$ 代替，$a\div 2$ 可以用 $a>>1$ 代替（$<<1$ 和 $\times 2$ 的速度是一样的，即使不开 O2，但 $>>1$ 速度比 $\div 2$ 快）。 - 建树时记录每个节点所对应的区间，就不需要每次计算当前节点的左右端点了，减小代码复杂度。 - 因为下标为 $a$ 的节点的左儿子下标为 $a\times 2$，右儿子下标为 $a\times 2+1$，所以可以： -- 2.11.0