记录一个鬼畜的bug。
正文
昨晚和室友以及JeremyGuo、SunIsMe、Evian等人颓联盟，结果晚上躺在床上横竖睡不着，感觉自己一点钟是醒的，两点钟是醒的，三点钟是醒的，然后突然对时间失去了概念，困得一批的同时开始了莫名的焦虑（想知道现在到底几点了，以及如果我现在睡着还能睡几个小时），终于在这黑暗与倦意的折磨之下忍不住看了一眼手机：6：30
情况变得更糟糕了，我进一步陷入了没睡好就得去上课的焦虑之中，结果就彻底睡不着了，在床上闭目养神到7点半起床上计算机网络课。
第一节课认真在听，第二节课同学做Pre我直接掉线，然后开始写实验代码，写了一会就把我正在写的、前几天组内讨论出来的一个改进方法X掉了...感觉很难受，于是在组内群里抒发了自己的难受，然后学长突然蹦出一个新方向，突然解决了一个卡脖子的问题，突然一切都好起来了！
于是一整个上午都在写代码，想尽快实践一下，中午回宿舍趴在桌子上睡了两小时，然后继续写，然后开始调试，很快啊...这个鬼畜的BUG暴露出来了。
struct Node {
int l {};
int r {};
};
static std::vector<Node> d;
static int _indexBuildBase (int l, int r) {
d.push_back({});
int u = d.size()-1;
if(l == r)
return u;
int mid = (l+r)>>1;
d[u].l = _indexBuildBase(l, mid);
d[u].r = _indexBuildBase(mid+1, r);
printf("values: %d %d\n", d[u].l, d[u].r);
printf("return: %d\n", u);
return u;
}以上是bug产生地点的简化版代码，该BUG的症状表现为对于d[u].l和d[u].r的赋值有时似乎“没有任何效果”，调用_indexBuildBase(1, N)，输出结果最后几行为：
values: 4980 5335
return: 4979
values: 4268 4979
return: 4267
values: 0 4267
return: 2845
values: 0 0
return: 1在倒数第三行，倒数第二个_indexBuildBase返回，而在倒数第二行的输出中，可以看到本应等于2845的d[u].r依然是0，赋值似乎根本没有完成！
但如果改成：
int L, R;
L = _indexBuildBase(l, mid);
R = _indexBuildBase(mid+1, r);
d[u].l = L, d[u].r = R;BUG就神秘地销声匿迹了！
这个BUG如此诡异以至于我一度怀疑是编译器出了问题（删掉多余的编译参数进行测试，甚至还为此试着将GCC回调两个版本进行了编译，不过没有卵用），甚至还动摇了我对编译器的信任！
于是出去喝了口水，回来之后继续delta debug，秉承着凡事皆需一试的思想，试着将d.push_back删掉，改成在最开始d.resize(10000)。
BUG消失了！
这是巧合吗？我先是愣了一下，很快一个绝妙的脑子从我的解释里钻了出来！
起初，为了能让线段树的节点堆积在一段连续的内存里（提高缓存利用率），我使用vector开辟线段树节点。众所周知，vector的实现方式是倍增，在大小不足以存放数据时将长度翻倍并寻找一段连续内存，整体搬迁过去，所以其中节点的地址时长会发生变化，左儿子右儿子的关系因此不能使用指针进行表示。于是我想当然地使用下标进行表示，vector在我眼中成了一个普通的数组。
当然vector并不是普通的数组！在
d[u].r = _indexBuildBase(mid+1, r);这一句话中其实包含两个函数调用，其一是_indexBuildBase(mid+1, r)，其二则是d[u]对vector的方括号运算符的调用！如果G++在编译这一段代码的过程中，决定先调用
d[u]并获得了u号元素的地址，然后再调用_indexBuildBase，在递归的过程中，d.push_back不断被调用，最终触发了vector的整段迁移机制，导致原先获取的u号元素的地址™过期了，最后赋值自然是无效的！
事不宜迟，反汇编：
TM的果然！这个BUG差点就成功挑拨了我对编译器的信赖！
之后
之前为了图方便好像有不少地方也用了类似写法...拆弹去了...
2021.12.17
测试结果出来了，有提升，但还不够，可惜。