2023暑假信友队集训结营总结

· · 个人记录

线段树的拓展应用——动态开点权值线段树

知识点讲解

动态开点线段树

故名思义，将要增加新的点，就对应的开此点，从而保证下标为值域，维护所存的值。

与普通线段树不同的是pushdown

如果左右儿子没有，在此操作下需要新建，可以利用计数变量tot进行计算

需要注意的是线段树的大小， 设值域的大小为S， 则每一次操作至多新建的点为log_2S个。所以线段树的大小就是O(nlogS)。这里值域为\left [-10^9, 10^9 \right]，所以大小为{30} \times {N}

需要注意的是mid = (l + r - 1) / 2，这样可以处理l,r均为负数

权值线段树

类似于对于线段树的每一叶子节点当成一个桶，如g_x表示大小为x的数出现过多少次。

例题引入

普通平衡树

可以通过动态开点的权值线段树进行计算

对于操作insert，相当于在权值线段树的位置x的值加1

对于操作del，相当于在权值线段树的位置x的值减1

对于操作rnk，相当于求有多少个数比x小，对应的区间查询也就是\left[-INF, x - 1 \right ]

对于操作kth，可以借平衡树的思想，当前左子树的权值如果小于k，递归到右子树，并且k要减去左子树的权值。否子这届递归至左子树即可

对于操作pre相当于查找kth(rnk(x) - 1)，即找到排名比x小的那一个数对应的值。

对于操作nxt相当于查找kth(rnk(x + 1))，因为排名定义为比当前数小的数的个数 +1，所以此处为x+1即可。

可持久化线段树 2

可以通过动态开点的权值线段树并且进行历史版本的维护从而进行计算

发现每一次操作至多有log_2n个点的多出，不妨对于每一次多出的点都连向其原本所在点

如图：

那么对于初始序列可以看成将每一个数都逐步插入线段树

求\left[ L, R \right]中的第k大数便是对于版本l-1，与版本r之间的权值之差，通过类似上一题的查找第k大的数的方法进行查询。

这是建树的过程

void build(int l, int r) {
    tot = 1;
    lfor(i, l, r) root[i] = ++ tot, insert(root[i - 1], root[i], a[i], 1);
}

结营总结

在这一个月中，我学到了许多新的算法，比如说操作树，线段树二次递归，四边形不等式等等。同时也结识到了很多大佬。我对于写题的心态也逐渐从模板化变成可以理解算法的主要思想，利用此构建程序的\textcolor{black}{\texttt{OIer}}了。比赛方面每次都在坚持爆0，但是每次比赛都新算法都丰富了我的视野，让我学习到了更多知识。最后，再祝大家在这一年例\textcolor{black}{\texttt{RP++}}