可持久化权值线段树，wiki上指出引入者名字叫黃嘉泰，名字缩写正好是某位主席名字，所以又叫做主席树。而本篇先介绍可持久化线段树，阅读本篇前你需要先了解线段树
概念 所谓的可持久化，意思是你能得到所有的历史版本，为了达到这个效果，当然可以每次修改的时候，先整体复制再修改，结果自然就是会爆内存。而事实上，由于每次修改最多改一条链，而其它分支可以重用。我们先拿链表做例子，如果有个链表内容是 1->2->3->4->5 ，现在我们把3修改成6，得到 1->2->6->4->5 ，但是后面的元素没有改动，所以我们可以把后面的元素直接重叠在一起使用，如下图：
graph LR; 1-->2 2-->3 3-->4 4-->5 1'-->2' 2'-->6 6-->4 这样，完全可以当成两条不同的链表使用，同时节省空间。而可持久化线段树做法与这一样，就是没变的部分还使用原来节点，所以这个实现不能使用之前介绍的堆式储存，要和平衡树一样动态开节点。
数据结构 假设我们的数据是以下这样
下标 1 2 3 4 数据 1 0 5 2 构建线段树后结果如下
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 冒号前面的两个数表示一条线段，冒号后表示的是数据，这个数据表示的是这个区间的和。
然后我们要把第3个元素从5改为1，构造第二棵线段树，首先复制一个root，包括儿子的指向也复制，得到
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 1,4':8-->1,2:1 1,4':8-->3,4:7
很多人在初始接触线段树的时候，一看到别人写一大堆代码就直接弃坑了，其实不要被它的外表所欺骗，线段树其实是相当好写的树结构了，而且理解起来其实很简单。要学会这个，你不能光会抄模板就会区间修改和求个区间和，因为实际应用经常会使用它的变形，还是在于理解（理解后背板）。
数据结构 首先，回想一下heap的结构，它使用一个数组，同时使用下标本身来表达父子关系，这样的方式能节省大量指针所需要的内存空间，以下也使用这种表示方法来表示一棵线段树，也就是说，这里介绍的，属于狭义线段树。假设我们的数据是以下这样
下标 1 2 3 4 5 6 7 8 数据 1 0 5 2 3 4 0 1 构建线段树后结果如下
graph TD; 1,8:16-->1,4:8 1,8:16-->5,8:8 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 5,8:8-->5,6:7 5,8:8-->7,8:1 5,6:7-->5,5:3 5,6:7-->6,6:4 7,8:1-->7,7:0 7,8:1-->8,8:1