动态开点线段树

众所周知，线段树要开 \(4\) 倍空间，但是这样会浪费许多空间，所以动态开点线段树就诞生了。

动态开点线段树适用于 \(n\) 比较大的情况，它没有优化时间复杂度，优化的是空间复杂度。具体的，我们不再用 \(p\times 2\) 和 \(p\times 2 + 1\) 作为 \(p\) 的左右儿子了，而用两个数组 \(ls_{p}\) 和 \(rs_{p}\) 来代表。我们在访问一个结点时，如果它没有，那么就创造。所以，结点只有在有需要的时候才被创建。当我们需要访问某个子区间时，才建立代表这个区间的子结点。

\(\mathcal{Code}\)

void updata(int &p, int l, int r, int x, int k) { // 相当于原来的 build，可以循环暴力修改
  if (!p) { // 如果没有当前结点
    p = ++cnt;
  }
  if (l == r) {
    minn[p] += k;
    return ;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) {
    updata(ls[p], l, mid, x, k);
  } else {
    updata(rs[p], mid + 1, r, x, k);
  }
  pushup(p);
}

int query(int p, int l, int r, int ql, int qr) {
  if (p == 0) { // 不存在，返回 0
    return 0;
  }
  if (ql <= l && qr >= r) {
    return minn[p];
  }
  int mid = (l + r) >> 1, ans = 1e9;
  if (ql <= mid) {
    ans = min(ans, query(ls[p], l, mid, ql, qr));
  }
  if (qr > mid) {
    ans = min(ans, query(rs[p], mid + 1, r, ql, qr));
  }
  return ans;
}