引入

我们在一般的线段树中，代码都是如下的：

void build(int x, int l, int r) {if (l == r) {tree[x].size = 1;return ;}int mid = (l + r) / 2;build(x * 2, l, mid);build(x * 2 + 1, mid + 1, r);updata(x);
}

这在普通的线段树当然可以。

但是权值线段树的区间往往大于 10910^9109 ，此时我们按照这样的思路来做就会发现空间会超限。

这时候我们就需要用到动态开点了。

思路

我们不会有建树操作，我们只会有插入操作。

当我们枚举到一个区间时，却发现这个区间之前没有枚举过，也就是这个区间没被记录过，我们就开一个节点来记录。

if (x == 0)x = ++cnt;

因为我们不再是按照一定的规律给点编号，我们就需要记录一下这个节点的左右儿子。（我用的时结构体）

struct node {int lson, rson, size;
} tree[10000005];

然后我们在分区间的时候不是两个区间都去枚举，而是我们要插入的数在那个区间就枚举那个。

int mid = (l + r) / 2;if (val <= mid)insert(tree[x].lson, l, mid, val);elseinsert(tree[x].rson, mid + 1, r, val);

我们来看看因为他每次最多开 log2(值域)log_2(值域)log2​(值域) 个节点，所以他一共就会开 nlog2(值域)nlog_2(值域)nlog2​(值域) 个节点，这样子我们就可以存的下了。

代码

struct node {int lson, rson, size;
} tree[10000005];
void insert(int &x, int l, int r, int val) {if (x == 0)//如果当我枚举到这个点时，我却没有记录，那我们就开一个节点x = ++cnt;tree[x].size++;if (l == r)return ;int mid = (l + r) / 2;if (val <= mid)//如果我要插入的值在左边，就搜左边，要不就搜右边insert(tree[x].lson, l, mid, val);elseinsert(tree[x].rson, mid + 1, r, val);updata(x);//更新这个点的状态
}