可修改主席树

可修改主席树

前言：这个就是传说中的树套树。。。

主席树

首先我们先简单的复习一下主席树（我的主席树入门）：
主席数实际上就是一种权值线段树
ta能解决的一个经典问题就是区间第K大（后来知道也可以用整体二分解决）

给定一个长度为n的序列，询问区间第K大
我们建了n棵权值线段树，每一棵线段树维护序列1~i的信息
查询的时候，计算区间元素个数t，与k比较，之后继续向左右结点查找

建树过程：

可修改

给定一个含有n个数的序列a[1]，a[2]，a[3]……a[n]，程序必须回答这样的询问：对于给定的i，j，k，在a[i]，a[i+1]，a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)
并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题

在普通的主席树中，我们每插入一个元素，相当于产生了一棵新的线段树
如果我们需要修改i位置的信息，ta会影响到i~n棵树
尽管修改是O(nlogn)级别的，但是由于牵扯到的树实在是太多了，这种方法显然会GG

于是我们想起了一种可以快速修改和获得前缀和的数据结构——树状数组

每次修改时只需要修改[j+lowbit(j)]等等的元素，每次需要对x,y两棵子树分别求前缀和[j-lowbit(j)]等等的和

这样修改和获取前缀和的复杂度都是logn的，所以每次操作都是(logn)^2的

再分析一下空间复杂度：

回顾之前，我们虽然建了n棵树但事实上很多部分是相同的，所以那些部分我们都没有管，只是将节点与上一个节点定为相同，然后对于变化的部分再操作

那么我们现在如果按照上面的方法大概是不太可行的，因为现在我们每棵线段树表示的是树状数组中的含义（例如6表示5+6,12表示9+10+11+12等等…）

也就是说每次修改的前驱可能不同，不能将前一个结点复制一下，在ta的基础上更改
（事实上，原来的建树方法是因为前驱只有一个以及只要修改一个，而我们这里两个都不满足）
但是这种思维是好的：
每次改变的都只有一条链，而每次修改就是添加一条链上去，不是整个线段树已经建好了再去修改

下面简单说一下怎么使用线段树的问题：

• 初始化：一开始我们需要离散化
  （注意：因为操作中有修改元素的操作，所以离散化需要将这些元素也包含在内，这就需要离线处理）
• 预处理：对于第i个元素，对i及i后面的（指树状数组中i+lowbit(i)的位置）所有节点都加上这个元素
• 修改：首先按原来的值在权值树状数组上-1，然后按新的值在权值树状数组上+1
• 询问：和静态类似，但是每次求左右子树的前缀和时使用树状数组

复杂度：

例题链接

题解