动态开点线段树+权值线段树概述

一开始觉得什么动态开点啥的都特别叼。实际上并没有什么，就是在空间不够的情况下，把不需要的节点变成虚点就好了，具体什么意思，我们来看一道题：P1908 逆序对

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj$a_i>a_j$且i<j$i<j$的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入格式：

第一行，一个数n$n$，表示序列中有n$n$个数。
第二行n$n$个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

说明
对于50%的数据，n≤2500$n\le 2500$
对于100%的数据，n≤40000$n\le 40000$。

$$
$$
$$
$$
$$

解：

这道题n2$n^2$暴力都会(其实nlogn$nlogn$也都会，可以用树状数组做)。但是我们闲的蛋疼，非要用线段树做。
考虑一下怎么做：我们从左到右遍历数组，对于每个数我们查询在它之前比它大的数有多少个。然后把它加入线段树。

现在我们的问题就变成了在线段树内查询x$x$ ~ inf$inf$大小的数有多少个。于是我们考虑权值线段树。

什么是权值线段树呢？我们以前的线段树都是维护数组的权值。现在我们要维护的是数组下标，我们就反其道而行之，把数组权值变成线段树下标，而维护数组区间内下标个数。

不对啊？我们会有一个问题。因为我们并不知道权值范围是多少，所以很有可能我们要开一个−inf$-inf$到inf$inf$的超大线段树，infloginf$infloginf$怕不是MLE了，其实inf$inf$怕不是都MLE。那我们咋办？

记得前面写的动态开点线段树么？我们可以看到其实最后我们最大就只会用到40000个叶子节点，而其它节点都是空的。所以我们并不一定要把这些空节点建出来。画个图理解一下：

就是说如果我们只insert 4 一个点，对于1-8的线段树只用建4（log8$log8$+1）个节点。那么对于一个节点来说，我们只需要建loginf$loginf$个点就可以把它加入线段树里。然后查询按正常查询即可。

但是这道题由于太水了，连pushdown$pushdown$和update$update$都没有，根本就不能说是一道线段树，你就假装它是一个线段树吧，可以脑补一下pushdown$pushdown$和update$update$，也挺简单的。

所以动态开点和权值线段树基本上是在一起的，所以笔者就放在一起讲啦！！！再来安利一道题：P2471 [SCOI2007]降雨量。这道如果你不想离散化的话，可以写写动态开点线段树。注意！！！心脏不好的请不要写这道题。