sjhBIT

RAND_MAX · 2024-11-08 10:56:20 · 生活·游记

一刻也没有为 fzxds 的开始而哀悼，迅速赶到战场的是 sjhBIT！！！

该数据结构最初构思于 CSP2024 的考场上，后格了 fzxds 而灵感迸发，故创此数据结构。想必这就是格物致知的妙处吧。

对于朴素 BIT 的单点修改，可以从节点 x 一路向上边跳边修改 x+lowbit(x) 直到达到根节点。我们注意到这种操作形如树上链加，所以我们可以将点 x 与 x+lowbit(x) 连边并树链剖分，用差分 BIT 进行区间修改，这样可以做到 O(\log^2n)。

对于查询，我们先考虑如何查询原 BIT 上的一个点，这是容易的，只需在差分 BIT 上查询前缀和即可，是 O(\log n) 的。考虑区间查询，同理，只需按朴素 BIT 进行前跳操作，同时用上面的方法访问到原 BIT 的节点即可，故时间复杂度是 O(\log^2 n) 的。

注意到差分 BIT 仍是朴素的，所以我们可以将差分 BIT 也转化为 sjhBIT 。我们称朴素 BIT 为零阶 BIT，sjhBIT 为一阶 BIT。只需循环嵌套便可以实现 +\infin 阶 BIT，可以帮助我们大大劣化单次操作的时间复杂度至 O(\log^{+\infin}n)。

由于 fzxds 可以实现区间修改单点查询，很难不发现若是实现更好可以将差分 BIT 转化成 fzxds，这样可以在不减少复杂度的前提下增加代码的趣味性与可读性，造福所有 OIer。