Charlie查理 @ 2022-11-18 09:08:55
做别的题时写线段树，正常是这么写的：
#define ls (i << 1)
#define rs (i << 1 | 1)然而我当时写错了，发现这样也能AC：
#define ls (mid << 1)
#define rs (mid << 1 | 1)不是很明白原理，求分析qwq
by whhsteven @ 2022-11-18 10:02:37
我试了线段树 3（Seg Beats + 区间历史最值），可以通过。内存使用量变小了，但是时间变长了，大概是访存不连续。
by reveal @ 2022-11-18 10:09:50
或许跟 黑科技：数组两倍空间线段树，实现方便 - chy-2003 是等价的？
by SmallBlack @ 2022-11-18 10:21:04
花了一点时间证明，这种存法不会重复
by _LX_ @ 2022-11-18 10:28:10
那看来就是时间换空间了，在一些题目里还是有点用处的。所以，从现在开始，这种做法叫做查理线段树，建议加入NOI大纲和OIWiki（bushi
by Charlie查理 @ 2022-11-18 10:52:56
@reveal 确实是等价的
by Charlie查理 @ 2022-11-18 10:53:12
@SmallBlack orz谢谢大佬
by Charlie查理 @ 2022-11-18 10:55:11
@whhsteven 可以细说一下啥是访存不连续吗 /kk
by whhsteven @ 2022-11-18 11:12:49
就是内存访问不连续。这相比于连续访问会有额外的时间开销。大概这样。
by Z_302 @ 2022-11-18 12:37:50
@whhsteven 能讲一下为啥会内存访问不连续吗 QwQ
by optimize_2 @ 2022-11-18 21:09:28
这为什么会不连续
我也不理解