动态主席树

动态主席树

写在前面

相对于静态主席树，动态主席树意味着，每个节点可能会修改称为新的值，按照我们平时的想法，一定是在之前要删除的位置上进行-1操作，然后再新插入的位置上+1

解析

静态主席树我们在每个节点处创建一个权值线段树，然后在区间[l,r]求解时，使用第r棵线段树 - 第l-1棵线段树，在这个线段树上进行查询第k大元素的离散位置，然后根据之前进行离散的结果，得到最终的位置

使用ZOJ-2112作为栗子，数据为：3 2 1 4 7 6

这里要把所有的数据，包括在下面需要进行修改的数据，一次性全部列举出来，然后进行离散操作，因为主席树是一种离线结构，在起始要将所有数据都列举出来，为其开辟空间，然后再进行操作，这就是主席树的局限

那么离散化之后的数据为：3 2 1 4 6 5 

同静态树状数组相同，使用数组T表示线段树的根节点

对于动态主席树，我们需要增加一些另外的线段树，这些线段树根节点假设用数组S表示，这些线段树只是用来维护修改节点的信息，那么我们要查询区间问题，怎么维护这样一个S数组呢？对于区间维护，树状数组是一个很好的选择

开始，我们的数组长度为5，那么我们就可以只维护S[1] ~S[5]，因为区间查询和修改的范围就是这些

当出现修改时，如：C 2 6 （将第二个位置上的数字改为6） 开始a[2] = 2,对应离散后位置2，那么就要在到达2位置的整条路径上进行-1操作，6对应离散后位置为5，那么就要在到达5位置的整条路径上进行+1操作，同时使用树状数组维护，需要同时更新相对应的树

在进行求解的时候，数组T对应的，使用和静态主席树相同的方法，对于S数组，需要使用树状数组区间求和的思想

程序

#include <iostream>
#i