关于我写错ls, rs定义却AC的这件事

Charlie查理 @ 2022-11-18 09:08:55

#define ls (i << 1)
#define rs (i << 1 | 1)

#define ls (mid << 1)
#define rs (mid << 1 | 1)

by Charlie查理 @ 2022-11-18 09:10:33

code with mid

code with i

两个代码只有 i 和 mid 的区别

by whhsteven @ 2022-11-18 09:27:15

我超，线段树新写法！

线段树上每个区间的 \mathrm{mid} 是互不相同的，所以把左右儿子分别存到 2\mathrm{mid} 和 2\mathrm{mid} +1 不会引起冲突。

那这样是不是以后线段树只用开 2 倍空间了啊！/se

by HJY2022 @ 2022-11-18 09:27:57

@Charlie查理 所有都错了不就是没错？毕竟只起到一个类似指针的错误，然后好像也不会重复

by HJY2022 @ 2022-11-18 09:28:32

@whhsteven 不太对吧...点数还是没变，没有本质区别

by HJY2022 @ 2022-11-18 09:29:32

我语文其实不好...不会写作文和阅读...

by whhsteven @ 2022-11-18 09:30:16

你考虑线段树上区间 \mathrm{mid} 的值域是 [1,n]，我最多只访问到 2n + 1 所以是 2 倍空间。

by ღꦿ࿐ @ 2022-11-18 09:32:06

@whhsteven [1,2] 的 mid 是 1 , [1,1] 的也是。

by SmallBlack @ 2022-11-18 09:32:10

经过尝试，楼主的代码中的N * 4改成N<<1也是可以过的

所以以后就用这种方法了（bushi）

by SmallBlack @ 2022-11-18 09:33:41

@ღꦿ࿐ 但是[1,1]就没有儿子节点了

by Ja50nY0un9_as_AgNO3 @ 2022-11-18 09:35:28

我用类似写法试了，然而挂了啊