houpingze 的博客

膜拜zqs,sx,zlt,ymw,qyh官方博客

浅谈zqs树

zqs树是一种能$O(1)$预处理、区间修改、区间取模、区间翻转、区间求最值、区间求各种子序列的高级数据结构,它由近代珂学家zqs巨佬与$1919$年发明,至今技术仍在完善中。

例题

研究成果及经历

现在,就让我们一起深入了解zqs树的各种操作。

值得一提的是,zqs树基于zqs巨发明的C--语言,想要下载的可以去这里zqs树仅能在此编写。

预处理

read_and_init();

这是zqs发明的$O(1)$预处理+读入的函数,想了解源代码可以自行去这里查看,不再赘述。

建出的树是这样的:

zqs本人描述,建树其实是随机的,只有他本人随机建树,之后的修改和询问才能达到$O(1)$的时间复杂度。

区间翻转

int l,r;
read(l,r);
a[l~r].Flip();

zqs树的函数Flip由于源代码并未公开,原理我们不得而知,想了解的可以去询问zqs

upd:菜鸡得到了@zqs 的回复,他说

你不懂,你太菜了。

区间查询

我们发现,由于zqs人品极好,一段序列在建出来的树上也是连续的。这样,我们就可以对每一条链套一个分块+线段树+平衡树。

代码过长,据zqs本人描述

大概也就是几百TB吧,不多。

由于zqs树极其深奥,作者需要研究一个世纪,未完待续。


2021-08-09 12:21:13 in 未分类