数据结构

二维线段树（四分版）

#define son0 l1, mid1, l2, mid2, rt << 2
#define son1 mid1 + 1, r1, l2, mid2, rt << 2 | 1
#define son2 l1, mid1, mid2 + 1, r2, rt << 2 | 2
#define son3 mid1 + 1, r1, mid2 + 1, r2, rt << 2 | 3
#define target nl1, nr1, nl2, nr2
const int N = 800;
const int M = 800;
int tr[2][16 * N * M + 1];
int an[N + 1][M + 1];

void update(int rt) {
  tr[0][rt] =
      max(tr[0][rt << 2],
          max(tr[0][rt << 2 | 1], max(tr[0][rt << 2 | 2], tr[0][rt << 2 | 3])));
  tr[1][rt] =
      min(tr[1][rt << 2],
          min(tr[1][rt << 2 | 1], min(tr[1][rt << 2 | 2], tr[1][rt << 2 | 3])));
}

void build(int l1, int r1, int l2, int r2, int rt) {
  int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
  tr[0][rt] = -1e9, tr[1][rt] = 1e9;
  if (r1 < l1 || r2 < l2) return;
  if (l1 == r1 && l2 == r2) {
    tr[0][rt] = tr[1][rt] = an[l1][l2];
    return;
  }
  build(son0), build(son1), build(son2), build(son3);
  update(rt);
}

void modify(int l1, int r1, int l2, int r2, int rt, int x1, int x2, int k) {
  int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
  if (r1 < l1 || r2 < l2) return;
  if (l1 == r1 && l2 == r2) {
    tr[0][rt] = k;
    tr[1][rt] = k;
    return;
  }
  if (x1 <= mid1 && x2 <= mid2)
    modify(son0, x1, x2, k);
  else if (x1 > mid1 && x2 <= mid2)
    modify(son1, x1, x2, k);
  else if (x1 <= mid1 && x2 > mid2)
    modify(son2, x1, x2, k);
  else
    modify(son3, x1, x2, k);
  update(rt);
}

int query_for_max(int l1, int r1, int l2, int r2, int rt, int nl1, int nr1,
                  int nl2, int nr2) {
  int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
  if (r1 < l1 || r2 < l2) return -1e9;
  if (l1 >= nl1 && r1 <= nr1 && l2 >= nl2 && r2 <= nr2) return tr[0][rt];
  int ans = -1e9;
  if (nl1 <= mid1 && nl2 <= mid2) ans = max(ans, query_for_max(son0, target));
  if (nr1 > mid1 && nl2 <= mid2) ans = max(ans, query_for_max(son1, target));
  if (nl1 <= mid1 && nr2 > mid2) ans = max(ans, query_for_max(son2, target));
  if (nr1 > mid1 && nr2 > mid2) ans = max(ans, query_for_max(son3, target));
  return ans;
}

int query_for_min(int l1, int r1, int l2, int r2, int rt, int nl1, int nr1,
                  int nl2, int nr2) {
  int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
  if (r1 < l1 || r2 < l2) return 1e9;
  if (l1 >= nl1 && r1 <= nr1 && l2 >= nl2 && r2 <= nr2) return tr[1][rt];
  int ans = 1e9;
  if (nl1 <= mid1 && nl2 <= mid2) ans = min(ans, query_for_min(son0, target));
  if (nr1 > mid1 && nl2 <= mid2) ans = min(ans, query_for_min(son1, target));
  if (nl1 <= mid1 && nr2 > mid2) ans = min(ans, query_for_min(son2, target));
  if (nr1 > mid1 && nr2 > mid2) ans = min(ans, query_for_min(son3, target));
  return ans;
}

二维线段树（树套树版）

#define clr(a, b) memset(a, b, sizeof(a))
const int maxn = 800 + 2;
struct Node {
  LL maxw, minw;
} tree[maxn << 2][maxn << 2];
int n, q;
LL minw, maxw;
void push_upy(int deep, int k) {
  tree[deep][k].minw =
      min(tree[deep][k << 1].minw, tree[deep][k << 1 | 1].minw);
  tree[deep][k].maxw =
      max(tree[deep][k << 1].maxw, tree[deep][k << 1 | 1].maxw);
  return;
}
void push_upx(int deep, int k) {
  tree[deep][k].minw =
      min(tree[deep << 1][k].minw, tree[deep << 1 | 1][k].minw);
  tree[deep][k].maxw =
      max(tree[deep << 1][k].maxw, tree[deep << 1 | 1][k].maxw);
  return;
}
void bulid_y(int ly, int ry, int deep, int k, int flag) {
  tree[deep][k].maxw = -inf;
  tree[deep][k].minw = inf;
  if (ly == ry) {
    if (flag) {
      scanf("%lld", &tree[deep][k].maxw);
      tree[deep][k].minw = tree[deep][k].maxw;
    } else {
      push_upx(deep, k);
    }  //更新x方向
    return;
  }
  int mind = (ly + ry) >> 1;
  bulid_y(ly, mind, deep, k << 1, flag);
  bulid_y(mind + 1, ry, deep, k << 1 | 1, flag);
  push_upy(deep, k);
  return;
}
void bulid_x(int lx, int rx, int deep) {
  if (lx == rx) {
    bulid_y(1, n, deep, 1, 1);
    return;
  }
  int mind = (lx + rx) >> 1;
  bulid_x(lx, mind, deep << 1);
  bulid_x(mind + 1, rx, deep << 1 | 1);
  bulid_y(1, n, deep, 1, 0);  //同区域y轴方向
  return;
}
void query_y(int ly, int ry, int Ly, int Ry, int deep, int k) {
  if (Ly <= ly && ry <= Ry) {
    minw = min(tree[deep][k].minw, minw);
    maxw = max(tree[deep][k].maxw, maxw);
    return;
  }
  int mind = (ly + ry) >> 1;
  if (Ly <= mind) query_y(ly, mind, Ly, Ry, deep, k << 1);
  if (Ry > mind) query_y(mind + 1, ry, Ly, Ry, deep, k << 1 | 1);
  return;
}
void query_x(int lx, int rx, int Lx, int Rx, int Ly, int Ry, int deep) {
  if (Lx <= lx && rx <= Rx) {
    query_y(1, n, Ly, Ry, deep, 1);
    return;
  }
  int mind = (lx + rx) >> 1;
  if (Lx <= mind) query_x(lx, mind, Lx, Rx, Ly, Ry, deep << 1);
  if (Rx > mind) query_x(mind + 1, rx, Lx, Rx, Ly, Ry, deep << 1 | 1);
  return;
}
void update_y(int ly, int ry, int y, int deep, int k, int flag) {
  if (ly == ry && ly == y) {
    if (flag)
      tree[deep][k].minw = tree[deep][k].maxw = floor((minw + maxw) / 2);
    else
      push_upx(deep, k);
    return;
  }
  int mind = (ly + ry) >> 1;
  if (y <= mind)
    update_y(ly, mind, y, deep, k << 1, flag);
  else
    update_y(mind + 1, ry, y, deep, k << 1 | 1, flag);
  push_upy(deep, k);
  return;
}
void update_x(int lx, int rx, int x, int y, int deep) {
  if (lx == rx && lx == x) {
    update_y(1, n, y, deep, 1, 1);
    return;
  }
  int mind = (lx + rx) >> 1;
  if (x <= mind)
    update_x(lx, mind, x, y, deep << 1);
  else
    update_x(mind + 1, rx, x, y, deep << 1 | 1);
  update_y(1, n, y, deep, 1, 0);
  return;
}

矩阵乘法线段树

struct trnode {
  int abc[3];
} tr[1200010], lazy1[1200010], lazy_0;

// lazy_0 = {0,0,0}
struct trlazy {
  int abc[3][3];
  bool equal(trlazy x) {
    for (int i = 0; i <= 2; i++)
      for (int j = 0; j <= 2; j++)
        if (this->abc[i][j] != x.abc[i][j]) return false;
    return true;
  }
} lazy2[1200010], lazy_1;

// lazy_1 = {{1,0,0},{0,1,0},{0,0,1}}
trlazy mul(trlazy x, trlazy y) {
  trlazy z;
  memset(z.abc, 0, sizeof(z.abc));
  for (int i = 0; i <= 2; i++)
    for (int j = 0; j <= 2; j++) {
      int tmp = x.abc[i][j];
      for (int k = 0; k <= 2; k++)
        z.abc[i][k] = (z.abc[i][k] + (long long)tmp * y.abc[j][k] % MOD) % MOD;
    }
  return z;
}

trnode mul(trlazy x, trnode y) {
  trnode z;
  for (int i = 0; i <= 2; i++) {
    int tmp = 0;
    for (int j = 0; j <= 2; j++)
      tmp = (tmp + (long long)x.abc[i][j] * y.abc[j] % MOD) % MOD;
    z.abc[i] = tmp;
  }
  return z;
}

trnode add(trnode x, trnode y) {
  trnode z;
  z.abc[0] = (x.abc[0] + y.abc[0]) % MOD;
  z.abc[1] = (x.abc[1] + y.abc[1]) % MOD;
  z.abc[2] = (x.abc[2] + y.abc[2]) % MOD;
  return z;
}

trnode mul(int k, trnode x) {
  x.abc[0] = (long long)x.abc[0] * k % MOD;
  x.abc[1] = (long long)x.abc[1] * k % MOD;
  x.abc[2] = (long long)x.abc[2] * k % MOD;
  return x;
}

void update(int rt) { tr[rt] = add(tr[rt << 1], tr[rt << 1 | 1]); }

void color1(int l, int r, int rt, trnode k) {
  lazy1[rt] = add(lazy1[rt], k);
  k = mul(r - l + 1, k);
  tr[rt] = add(tr[rt], k);
}

void color2(int l, int r, int rt, trlazy k) {
  lazy2[rt] = mul(k, lazy2[rt]);
  lazy1[rt] = mul(k, lazy1[rt]);
  tr[rt] = mul(k, tr[rt]);
}

void push_col1(int l, int r, int rt) {
  if (lazy1[rt].abc[0] != 0 || lazy1[rt].abc[1] != 0 || lazy1[rt].abc[2] != 0) {
    int mid = (l + r) >> 1;
    color1(l, mid, rt << 1, lazy1[rt]);
    color1(mid + 1, r, rt << 1 | 1, lazy1[rt]);
    lazy1[rt] = lazy_0;
  }
}

void push_col2(int l, int r, int rt) {
  if (!lazy2[rt].equal(lazy_1)) {
    int mid = (l + r) >> 1;
    color2(l, mid, rt << 1, lazy2[rt]);
    color2(mid + 1, r, rt << 1 | 1, lazy2[rt]);
    lazy2[rt] = lazy_1;
  }
}

void modify(int l, int r, int rt, int nl, int nr, trnode k) {
  if (l >= nl && r <= nr) {
    color1(l, r, rt, k);
    return;
  }
  push_col2(l, r, rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) modify(l, mid, rt << 1, nl, nr, k);
  if (nr > mid) modify(mid + 1, r, rt << 1 | 1, nl, nr, k);
  update(rt);
}

void modify(int l, int r, int rt, int nl, int nr, trlazy k) {
  if (l >= nl && r <= nr) {
    color2(l, r, rt, k);
    return;
  }
  push_col2(l, r, rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) modify(l, mid, rt << 1, nl, nr, k);
  if (nr > mid) modify(mid + 1, r, rt << 1 | 1, nl, nr, k);
  update(rt);
}

int query(int l, int r, int rt, int nl, int nr, int x) {
  if (l >= nl && r <= nr) return tr[rt].abc[x];
  push_col2(l, r, rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1, ans = 0;
  if (nl <= mid) ans = (ans + query(l, mid, rt << 1, nl, nr, x)) % MOD;
  if (nr > mid) ans = (ans + query(mid + 1, r, rt << 1 | 1, nl, nr, x)) % MOD;
  return ans;
}

void build(int l, int r, int rt) {
  lazy2[rt] = lazy_1;
  lazy1[rt] = lazy_0;
  tr[rt] = lazy_0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  update(rt);
}

单标记线段树

LL tr[4 * M], lazy[4 * M];
LL an[4 * M];

void update(int rt) { tr[rt] = tr[rt << 1] + tr[rt << 1 | 1]; }

void color(int l, int r, int rt, LL k) {
  lazy[rt] += k;
  tr[rt] += (r - l + 1) * k;
}

void push_col(int l, int r, int rt) {
  if (lazy[rt]) {
    int mid = (l + r) >> 1;
    color(l, mid, rt << 1, lazy[rt]);
    color(mid + 1, r, rt << 1 | 1, lazy[rt]);
    lazy[rt] = 0;
  }
}

void build(int l, int r, int rt) {
  if (l == r) {
    tr[rt] = an[l];
    lazy[rt] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  update(rt);
}

void modify(int l, int r, int rt, int nl, int nr, LL k) {
  if (l >= nl && r <= nr) {
    color(l, r, rt, k);
    return;
  }
  push_col(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) modify(l, mid, rt << 1, nl, nr, k);
  if (nr > mid) modify(mid + 1, r, rt << 1 | 1, nl, nr, k);
  update(rt);
}

LL query(int l, int r, int rt, int nl, int nr) {
  if (l >= nl && r <= nr) return tr[rt];
  push_col(l, r, rt);
  int mid = (l + r) >> 1;
  LL ans = 0;
  if (nl <= mid) ans += query(l, mid, rt << 1, nl, nr);
  if (nr > mid) ans += query(mid + 1, r, rt << 1 | 1, nl, nr);
  return ans;
}

双标记线段树

int tr[4 * N], lazy1[4 * N], lazy2[4 * N], p, an[4 * N];

void update(int rt) { tr[rt] = (tr[rt << 1] + tr[rt << 1 | 1]) % p; }

void color1(int l, int r, int rt, int k) {
  lazy1[rt] = (lazy1[rt] + k) % p;
  tr[rt] = (tr[rt] + (1LL * k * (r - l + 1) % p)) % p;
}

void color2(int rt, int k) {
  lazy2[rt] = (1LL * lazy2[rt] * k) % p;
  lazy1[rt] = (1LL * lazy1[rt] * k) % p;
  tr[rt] = (1LL * tr[rt] * k) % p;
}

void push_col1(int l, int r, int rt) {
  if (lazy1[rt]) {
    int mid = (l + r) >> 1;
    color1(l, mid, rt << 1, lazy1[rt]);
    color1(mid + 1, r, rt << 1 | 1, lazy1[rt]);
    lazy1[rt] = 0;
  }
}

void push_col2(int rt) {
  if (lazy2[rt] != 1) {
    color2(rt << 1, lazy2[rt]);
    color2(rt << 1 | 1, lazy2[rt]);
    lazy2[rt] = 1;
  }
}

void build(int l, int r, int rt) {
  lazy1[rt] = 0;
  lazy2[rt] = 1;
  if (l == r) {
    tr[rt] = an[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  update(rt);
}

void modify1(int l, int r, int rt, int nl, int nr, int k) {
  if (l >= nl && r <= nr) {
    color1(l, r, rt, k);
    return;
  }
  push_col2(rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) modify1(l, mid, rt << 1, nl, nr, k);
  if (nr > mid) modify1(mid + 1, r, rt << 1 | 1, nl, nr, k);
  update(rt);
}

void modify2(int l, int r, int rt, int nl, int nr, int k) {
  if (l >= nl && r <= nr) {
    color2(rt, k);
    return;
  }
  push_col2(rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1;
  if (nl <= mid) modify2(l, mid, rt << 1, nl, nr, k);
  if (nr > mid) modify2(mid + 1, r, rt << 1 | 1, nl, nr, k);
  update(rt);
}

int query(int l, int r, int rt, int nl, int nr) {
  if (l >= nl && r <= nr) return tr[rt];
  push_col2(rt);
  push_col1(l, r, rt);
  int mid = (l + r) >> 1;
  int ans = 0;
  if (nl <= mid) ans = (ans + query(l, mid, rt << 1, nl, nr)) % p;
  if (nr > mid) ans = (ans + query(mid + 1, r, rt << 1 | 1, nl, nr)) % p;
  return ans;
}

吉老师线段树（赋值和加的双标记处理法）

update_add 区间加
update_min 区间对常数k取min
query_add 区间求和
query_maxa 区间最大值
query_maxb 区间历史最大值

int x, y, k;
struct tree {
  LL sum;
  int add_a, add_a1, add_b, add_b1;
  int l, r, maxa, se, maxb, cnt;
} s[2000005];
LL an[2000005];

inline void update(int rt) {
  s[rt].maxa = max(s[rt << 1].maxa, s[rt << 1 | 1].maxa);
  s[rt].maxb = max(s[rt << 1].maxb, s[rt << 1 | 1].maxb);
  s[rt].sum = s[rt << 1].sum + s[rt << 1 | 1].sum;
  if (s[rt << 1].maxa == s[rt << 1 | 1].maxa) {
    s[rt].se = max(s[rt << 1].se, s[rt << 1 | 1].se);
    s[rt].cnt = s[rt << 1].cnt + s[rt << 1 | 1].cnt;
  }
  if (s[rt << 1].maxa > s[rt << 1 | 1].maxa) {
    s[rt].se = max(s[rt << 1].se, s[rt << 1 | 1].maxa);
    s[rt].cnt = s[rt << 1].cnt;
  }
  if (s[rt << 1].maxa < s[rt << 1 | 1].maxa) {
    s[rt].se = max(s[rt << 1].maxa, s[rt << 1 | 1].se);
    s[rt].cnt = s[rt << 1 | 1].cnt;
  }
}

void build(int l, int r, int rt) {
  s[rt].l = l, s[rt].r = r;
  if (l == r) {
    s[rt].sum = s[rt].maxa = s[rt].maxb = an[l];
    s[rt].se = -1e9;
    s[rt].cnt = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  update(rt);
}

inline void color(int k1, int k2, int k3, int k4, int rt) {
  s[rt].sum +=
      1ll * k1 * s[rt].cnt + 1ll * k3 * (s[rt].r - s[rt].l + 1 - s[rt].cnt);
  s[rt].maxb = max(s[rt].maxb, s[rt].maxa + k2);
  s[rt].add_b = max(s[rt].add_b, s[rt].add_a + k2);
  s[rt].add_b1 = max(s[rt].add_b1, s[rt].add_a1 + k4);
  s[rt].maxa += k1, s[rt].add_a += k1;
  s[rt].add_a1 += k3;
  if (s[rt].se != -1e18) s[rt].se += k3;
}

inline void push_col(int rt) {
  int maxn = max(s[rt << 1].maxa, s[rt << 1 | 1].maxa);
  if (s[rt << 1].maxa == maxn)
    color(s[rt].add_a, s[rt].add_b, s[rt].add_a1, s[rt].add_b1, rt << 1);
  else
    color(s[rt].add_a1, s[rt].add_b1, s[rt].add_a1, s[rt].add_b1, rt << 1);
  if (s[rt << 1 | 1].maxa == maxn)
    color(s[rt].add_a, s[rt].add_b, s[rt].add_a1, s[rt].add_b1, rt << 1 | 1);
  else
    color(s[rt].add_a1, s[rt].add_b1, s[rt].add_a1, s[rt].add_b1, rt << 1 | 1);
  s[rt].add_a = s[rt].add_b = s[rt].add_a1 = s[rt].add_b1 = 0;
}

void update_add(int rt) {
  if (s[rt].l > y || s[rt].r < x) return;
  if (x <= s[rt].l && s[rt].r <= y) return color(k, k, k, k, rt);
  push_col(rt);
  update_add(rt << 1), update_add(rt << 1 | 1);
  update(rt);
}

void update_min(int rt) {
  if (s[rt].l > y || s[rt].r < x || k >= s[rt].maxa) return;
  if (x <= s[rt].l && s[rt].r <= y && k > s[rt].se)
    return color(k - s[rt].maxa, k - s[rt].maxa, 0, 0, rt);
  push_col(rt);
  update_min(rt << 1), update_min(rt << 1 | 1);
  update(rt);
}

LL query_add(int rt) {
  if (s[rt].l > y || s[rt].r < x) return 0;
  if (x <= s[rt].l && s[rt].r <= y) return s[rt].sum;
  push_col(rt);
  return query_add(rt << 1) + query_add(rt << 1 | 1);
}

int query_maxa(int rt) {
  if (s[rt].l > y || s[rt].r < x) return -1e9;
  if (x <= s[rt].l && s[rt].r <= y) return s[rt].maxa;
  push_col(rt);
  return max(query_maxa(rt << 1), query_maxa(rt << 1 | 1));
}

int query_maxb(int rt) {
  if (s[rt].l > y || s[rt].r < x) return -1e9;
  if (x <= s[rt].l && s[rt].r <= y) return s[rt].maxb;
  push_col(rt);
  return max(query_maxb(rt << 1), query_maxb(rt << 1 | 1));
}

可持久化线段树（支持树套树思路）

主席树相关需先进行离散化

struct trnode {
  int lc, rc, c;
} tr[30 * N];

// logn * n的大小
void build(int l, int r, int &rt) {
  if (rt == 0) rt = ++len;
  if (l == r) {
    tr[rt].c = an[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, tr[rt].lc);
  build(mid + 1, r, tr[rt].rc);
}

void modify(int l, int r, int &rt, int x, int k) {
  if (rt == 0) rt = ++len;
  if (l == r) {
    tr[rt].c = k;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    modify(l, mid, tr[rt].lc, x, k);
  else
    modify(mid + 1, r, tr[rt].rc, x, k);
}

void add(int l, int r, int &rt, int x) {
  if (rt == 0) rt = ++len;
  tr[rt].c++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    add(l, mid, tr[rt].lc, x);
  else
    add(mid + 1, r, tr[rt].rc, x);
}

void merge(int &x, int y) {
  if (y == 0) return;
  if (x == 0) {
    x = y;
    return;
  }
  // tr[x].c += tr[y].c;
  //不同情况下采用不同修改操作
  merge(tr[x].lc, tr[y].lc);
  merge(tr[x].rc, tr[y].rc);
}

int query(int x, int y, int l, int r, int k) {
  if (l == r) return an[l];  //返回原数据中排名为l的数
  int lcx = tr[x].lc, lcy = tr[y].lc;
  int rcx = tr[x].rc, rcy = tr[y].rc;
  int mid = (l + r) >> 1;
  int cc = tr[lcx].c - tr[lcy].c;
  if (k <= cc)
    return query(lcx, lcy, l, mid, k);
  else
    return query(rcx, rcy, mid + 1, r, k - cc);
}

//查询区间中排名为k的数
int get_k(int l, int r, int x, int k) {
  if (l == r) return tr[x].c;
  int mid = (l + r) >> 1;
  if (k <= mid)
    return get_k(l, mid, tr[x].lc, k);
  else
    return get_k(mid + 1, r, tr[x].rc, k);
}  //查询第x个历史版本下第k个数

非旋Treap

split给了俩写法，一个是根据具体的值（普通平衡树）一个是根据前面有多少个数（区间翻转）

struct Treap {
  int siz[N], val[N], lson[N], rson[N], key[N];
  int flag[N];
  int tot;
  int root;

  void init() {
    tot = 0;
    root = newnode(inf);
    siz[root] = 0;
    srand(time(nullptr));
  }

  int newnode(int v) {
    ++tot;
    val[tot] = v;
    siz[tot] = 1;
    key[tot] = rand();
    lson[tot] = rson[tot] = 0;
    return tot;
  }

  void update(int x) { siz[x] = siz[lson[x]] + siz[rson[x]] + 1; }

  void push_down(int x) {
    swap(lson[x], rson[x]);
    if (lson[x]) flag[lson[x]] ^= 1;
    if (rson[x]) flag[rson[x]] ^= 1;
    flag[x] = 0;
  }

  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (key[x] < key[y]) {
      if (flag[x]) push_down(x);
      rson[x] = merge(rson[x], y);
      update(x);
      return x;
    }
    if (flag[y]) push_down(y);
    lson[y] = merge(x, lson[y]);
    update(y);
    return y;
  }

  void split_reverse(int rt, int k, int &x, int &y) {
    if (!rt) {
      x = y = 0;
      return;
    }
    if (flag[rt]) push_down(rt);
    if (siz[lson[rt]] < k)
      x = rt, split_reverse(rson[rt], k - siz[lson[rt]] - 1, rson[rt], y);
    else
      y = rt, split_reverse(lson[rt], k, x, lson[rt]);
    update(rt);
  }

  void split(int rt, int k, int &x, int &y) {
    if (!rt) {
      x = y = 0;
      return;
    }
    if (flag[rt]) push_down(rt);
    if (val[rt] <= k)
      x = rt, split(rson[rt], k, rson[rt], y);
    else
      y = rt, split(lson[rt], k, x, lson[rt]);
    update(rt);
  }

  void reverse(int l, int r) {
    int a, b, c;
    split_reverse(root, l - 1, a, b);
    split_reverse(b, r - l + 1, b, c);
    flag[b] ^= 1;
    root = merge(a, merge(b, c));
  }

  void insert(int v) {
    int x = 0, y = 0, z = newnode(v);
    split(root, v, x, y);
    x = merge(x, z);
    root = merge(x, y);
  }

  void remove(int v) {
    int x = 0, y = 0, z = 0;
    split(root, v, x, y);
    split(x, v - 1, x, z);
    z = merge(lson[z], rson[z]);
    x = merge(x, z);
    root = merge(x, y);
  }

  int find(int rt, int rank) {
    while (siz[lson[rt]] + 1 != rank) {
      if (siz[lson[rt]] >= rank)
        rt = lson[rt];
      else {
        rank -= siz[lson[rt]] + 1;
        rt = rson[rt];
      }
    }
    return val[rt];
  }

  int rank(int v) {
    int x = 0, y = 0;
    split(root, v - 1, x, y);
    int res = siz[x] + 1;
    root = merge(x, y);
    return res;
  }

  int Kth(int rnk) { return find(root, rnk); }

  int lower(int v) {
    int x = 0, y = 0;
    split(root, v - 1, x, y);
    int res = find(x, siz[x]);
    root = merge(x, y);
    return res;
  }

  int upper(int v) {
    int x = 0, y = 0;
    split(root, v, x, y);
    int res = find(y, 1);
    root = merge(x, y);
    return res;
  }

  void coutt(int i) {
    if (!i) return;
    if (flag[i]) push_down(i);
    coutt(lson[i]);
    cout << val[i] << ' ';
    coutt(rson[i]);
  }
};

分块平衡树

struct PHS {
 private:
  vector<vector<int>> v_a;

 private:
  vector<int> v_b;

 private:
  vector<int>::iterator v_it;

 private:
  int v_fnd(int v_vl) {
    if (v_a.size() == 1 && v_a[0].size() == 0) return 0;
    int v_l = 0, v_r = v_a.size() - 1, v_ps = v_a.size() - 1, v_md;
    while (v_l <= v_r) {
      v_md = (v_l + v_r) >> 1;
      if (v_a[v_md][v_a[v_md].size() - 1] >= v_vl) {
        v_ps = v_md;
        v_r = v_md - 1;
      } else
        v_l = v_md + 1;
    }
    return v_ps;
  }

 private:
  void v_spl(int v_ps) {
    v_b.insert(v_b.begin(), v_a[v_ps].end() - v_sz, v_a[v_ps].end());
    v_a[v_ps].erase(v_a[v_ps].end() - v_sz, v_a[v_ps].end());
    v_a.insert(v_a.begin() + v_ps + 1, v_b);
    v_b.clear();
    return;
  }

 private:
  void v_mrg(int v_ps) {
    v_a[v_ps].insert(v_a[v_ps].end(), v_a[v_ps + 1].begin(),
                     v_a[v_ps + 1].end());
    v_a.erase(v_a.begin() + v_ps + 1);
    return;
  }

 public:
  void v_ins(int v_vl) {
    if (v_a.size() == 0) {
      v_b.push_back(v_vl);
      v_a.push_back(v_b);
      v_b.clear();
      return;
    }
    int v_ps = v_fnd(v_vl);
    v_a[v_ps].insert(lower_bound(v_a[v_ps].begin(), v_a[v_ps].end(), v_vl),
                     v_vl);
    if (v_a[v_ps].size() >= (v_sz << 1)) v_spl(v_ps);
    return;
  }

 public:
  void v_ers(int v_vl) {
    int v_ps = v_fnd(v_vl);
    v_a[v_ps].erase(lower_bound(v_a[v_ps].begin(), v_a[v_ps].end(), v_vl));
    if (v_a[v_ps].size() <= (v_sz >> 1)) {
      if (v_a.size() == 1) return;
      if (v_ps == 0) {
        v_mrg(v_ps);
        return;
      }
      if (v_ps == v_a.size() - 1) {
        v_mrg(v_ps - 1);
        return;
      }
      v_mrg(v_ps - (v_a[v_ps - 1].size() < v_a[v_ps + 1].size()));
      return;
    }
    return;
  }

 public:
  int v_rnk(int v_vl) {
    int v_ps = v_fnd(v_vl), v_ns = 1;
    for (int i = 0; i < v_ps; i++) v_ns += v_a[i].size();
    v_ns += lower_bound(v_a[v_ps].begin(), v_a[v_ps].end(), v_vl) -
            v_a[v_ps].begin();
    return v_ns;
  }

 public:
  int v_kth(int v_rk) {
    v_rk--;
    int v_ps = 0;
    while (v_rk >= v_a[v_ps].size()) v_rk -= v_a[v_ps++].size();
    return v_a[v_ps][v_rk];
  }

 public:
  int v_pre(int v_vl) {
    int v_ps = v_fnd(v_vl);
    v_it = lower_bound(v_a[v_ps].begin(), v_a[v_ps].end(), v_vl);
    if (v_it == v_a[v_ps].begin())
      return v_a[v_ps - 1][v_a[v_ps - 1].size() - 1];
    return (*(--v_it));
  }

 public:
  int v_suf(int v_vl) {
    int v_ps = v_fnd(v_vl + 1);
    v_it = upper_bound(v_a[v_ps].begin(), v_a[v_ps].end(), v_vl);
    if (v_it == v_a[v_ps].end()) return v_a[v_ps + 1][0];
    return (*v_it);
  }
};

pb_ds

#include <ext/pb_ds/assoc_container.hpp>  // 因为tree定义在这里 所以需要包含这个头文件
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
__gnu_pbds ::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
                  Node_Update = null_tree_node_update,
                  Allocator = std::allocator<char> >

模板形参

Key: 储存的元素类型，如果想要存储多个相同的 Key 元素，则需要使用类似于 std::pair 和 struct 的方法，并配合使用 lower_bound 和 upper_bound 成员函数进行查找
Mapped: 映射规则（Mapped-Policy）类型，如果要指示关联容器是集合，类似于存储元素在 std::set 中，此处填入 null_type，低版本 g++ 此处为 null_mapped_type；如果要指示关联容器是 带值的集合，类似于存储元素在 std::map 中，此处填入类似于 std::map<Key, Value> 的 Value 类型
Cmp_Fn: 关键字比较函子，例如 std::less<Key>
Tag: 选择使用何种底层数据结构类型，默认是 rb_tree_tag。__gnu_pbds 提供不同的三种平衡树，分别是：
rb_tree_tag：红黑树，一般使用这个，后两者的性能一般不如红黑树
splay_tree_tag：splay 树
ov_tree_tag：有序向量树，只是一个由 vector 实现的有序结构，类似于排序的 vector 来实现平衡树，性能取决于数据想不想卡你
Node_Update：用于更新节点的策略，默认使用 null_node_update，若要使用 order_of_key 和 find_by_order 方法，需要使用 tree_order_statistics_node_update
Allocator：空间分配器类型

构造方式

__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
                 std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    trr;

成员函数

insert(x)：向树中插入一个元素 x，返回 std::pair<point_iterator, bool>。
erase(x)：从树中删除一个元素/迭代器 x，返回一个 bool 表明是否删除成功。
order_of_key(x)：返回 x 以 Cmp_Fn 比较的排名。
find_by_order(x)：返回 Cmp_Fn 比较的排名所对应元素的迭代器。
lower_bound(x)：以 Cmp_Fn 比较做 lower_bound，返回迭代器。
upper_bound(x)：以 Cmp_Fn 比较做 upper_bound，返回迭代器。
join(x)：将 x 树并入当前树，前提是两棵树的类型一样，x 树被删除。
split(x,b)：以 Cmp_Fn 比较，小于等于 x 的属于当前树，其余的属于 b 树。
empty()：返回是否为空。
size()：返回大小。

树剖

前置：线段树、建树

支持操作：路径区间加、路径求和、子树加、子树求和

两个lca函数分别支持路径加和路径求和

int an[M], ver[M * 2], nxt[M * 2], head[M], tot;
int fa[M], rnk[M], id[M], son[M], size[M], le[M], ri[M], dep[M], top[M];

void dfs1(int x) {
  size[x] = 1;
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x]) {
      fa[ver[i]] = x;
      dep[ver[i]] = dep[x] + 1;
      dfs1(ver[i]);
      size[x] += size[ver[i]];
      if (size[ver[i]] > size[son[x]]) son[x] = ver[i];
    }
}

void dfs2(int x, int t) {
  top[x] = t;
  rnk[x] = ++cnt;
  id[cnt] = x;
  le[x] = cnt;  // le,ri数组是用来记dfs序上以x为根节点的子树所在区间的左右端点
  if (!son[x]) {
    ri[x] = cnt;
    return;
  }
  dfs2(son[x], t);
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x] && ver[i] != son[x]) dfs2(ver[i], ver[i]);
  ri[x] = cnt;
}

//对树进行两次dfs以将轻重链剖分出来
void lca1(int x, int y, int z) {
  int fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] <= dep[fy]) {
      modify(1, n, 1, rnk[fy], rnk[y], z);
      y = fa[fy], fy = top[y];
    } else {
      modify(1, n, 1, rnk[fx], rnk[x], z);
      x = fa[fx], fx = top[x];
    }
  }
  if (dep[x] > dep[y])
    modify(1, n, 1, rnk[y], rnk[x], z);
  else
    modify(1, n, 1, rnk[x], rnk[y], z);
}

int lca2(int x, int y) {
  int fx = top[x], fy = top[y];
  int ans = 0;
  while (fx != fy) {
    if (dep[fx] <= dep[fy]) {
      ans += query(1, n, 1, rnk[fy], rnk[y]);
      ans %= p;
      y = fa[fy], fy = top[y];
    } else {
      ans += query(1, n, 1, rnk[fx], rnk[x]);
      ans %= p;
      x = fa[fx], fx = top[x];
    }
  }
  if (dep[x] > dep[y]) {
    ans += query(1, n, 1, rnk[y], rnk[x]);
    ans %= p;
  } else {
    ans += query(1, n, 1, rnk[x], rnk[y]);
    ans %= p;
  }
  return ans;
}

ST表

$O(1)$解决RMQ问题

int an[100010], st[100010][20];
int lg[100010];
int l, r, n, m;

void build() {
  for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
  for (int i = 1; i <= n; i++) st[i][0] = an[i];
  for (int j = 1; j <= 17; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

int query(int nl, int nr) {
  int cnt = lg[nr - nl + 1];
  return max(st[nl][cnt], st[nr - (1 << cnt) + 1][cnt]);
}

单调队列

解决固定长度区间极值问题

int n, k, x;
pair<int, int> queue_1[1000010];
int hed_1 = 1, tal_1 = 0;
pair<int, int> queue_2[1000010];
int hed_2 = 1, tal_2 = 0;
int ans1[1000010], ans2[1000010], tot;
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    while (hed_1 <= tal_1 && queue_1[tal_1].first < x) tal_1--;
    while (hed_2 <= tal_2 && queue_2[tal_2].first > x) tal_2--;
    queue_1[++tal_1] = make_pair(x, i);
    queue_2[++tal_2] = make_pair(x, i);
    while (hed_1 <= tal_1 && i - queue_1[hed_1].second >= k) hed_1++;
    while (hed_2 <= tal_2 && i - queue_2[hed_2].second >= k) hed_2++;
    if (i >= k) {
      ans1[++tot] = queue_1[hed_1].first;
      ans2[tot] = queue_2[hed_2].first;
    }
  }
  return 0；
}

树状数组

效率比线段树要高且好写，所占空间也较小

#define lb(x) x&(-x)
const int N = 5e5 + 10;
int tree[N], n;
int query(int k) {
  int ans = 0;
  while (k > 0) {
    ans += tree[k];
    k -= lb(k);
  }
  return ans;
}

void update(int k, int x) {
  while (k <= n) {
    tree[k] += x;
    k += lb(k);
  }
}

莫队(小Z的袜子)

int c[MAXN], belong[MAXN], num[MAXN];
LL tot = 0, ans1[MAXN], ans2[MAXN];

struct ask {
  int l, r, id;
};

ask b[MAXN];

bool cmp(const ask& a, const ask& b) {
  return belong[a.l] ^ belong[b.l] ? belong[a.l] < belong[b.l]
         : belong[a.l] & 1         ? a.r < b.r
                                   : a.r > b.r;
}

void add(int x) {
  tot += (num[x] << 1) | 1;
  num[x]++;
}

void del(int x) {
  tot -= (num[x] << 1) - 1;
  num[x]--;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int block = n / sqrt((m << 1) / 3);
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
    belong[i] = (i - 1) / block + 1;
  }
  for (int i = 1; i <= m; ++i) {
    cin >> b[i].l >> b[i].r;
    b[i].id = i;
  }
  sort(b + 1, b + 1 + m, cmp);
  for (int i = 1, l = 1, r = 0; i <= m; ++i) {
    if (b[i].l == b[i].r) {
      ans1[b[i].id] = 0;
      ans2[b[i].id] = 1;
      continue;
    }
    while (l < b[i].l) del(c[l++]);
    while (l > b[i].l) add(c[--l]);
    while (r < b[i].r) add(c[++r]);
    while (r > b[i].r) del(c[r--]);
    ans1[b[i].id] = tot - (b[i].r - b[i].l + 1);
    ans2[b[i].id] = (LL)(b[i].r - b[i].l + 1) * (b[i].r - b[i].l);
    LL g = __gcd(ans1[b[i].id], ans2[b[i].id]);
    ans1[b[i].id] /= g;
    ans2[b[i].id] /= g;
  }
  for (int i = 1; i <= m; ++i) {
    cout << ans1[i] << "/" << ans2[i] << "\n";
  }
  return 0;
}

KD树

解决无限的二维平面上有限个点的区间加、区间求和以及求最近邻。尤其适合求最近邻

const LL N = 10010;
const double INF = 1e18;
const LL dimension = 2;
LL D;

struct Node {
  double d[dimension], maxpos[dimension], minpos[dimension];
  LL v, sum, lazy, cnt;
  //以中心点d作为空间的代表，max和min分别是空间的边界
  LL l, r;

  bool operator<(const Node &b) const { return d[D] < b.d[D]; }

  bool operator==(const Node &b) const {
    int ans = 1;
    for (int i = 0; i < dimension; i++) {
      ans &= d[i] == b.d[i];
    }
    return ans;
  }
} p[N];

bool in(double x1, double y1, double x2, double y2, double X1, double Y1,
        double X2, double Y2) {
  return x1 <= X1 && X2 <= x2 && y1 <= Y1 && Y2 <= y2;
}

bool out(double x1, double y1, double x2, double y2, double X1, double Y1,
         double X2, double Y2) {
  return x1 > X2 || x2 < X1 || y1 > Y2 || y2 < Y1;
}

struct KDT {
  LL root{}, cnt{}, block{};
  Node tr[N]{}, now{};

  // now,用来单点插入
  void update(LL rt) {
    tr[rt].cnt = 1;
    LL l = tr[rt].l, r = tr[rt].r;
    if (l) tr[rt].cnt += tr[l].cnt;
    if (r) tr[rt].cnt += tr[r].cnt;
    for (int i = 0; i < dimension; i++) {
      tr[rt].maxpos[i] = tr[rt].minpos[i] = tr[rt].d[i];
      if (l) {
        tr[rt].minpos[i] = min(tr[rt].minpos[i], tr[l].minpos[i]);
        tr[rt].maxpos[i] = max(tr[rt].maxpos[i], tr[l].maxpos[i]);
      }
      if (r) {
        tr[rt].minpos[i] = min(tr[rt].minpos[i], tr[r].minpos[i]);
        tr[rt].maxpos[i] = max(tr[rt].maxpos[i], tr[r].maxpos[i]);
      }
    }
    tr[rt].sum = tr[l].sum + tr[r].sum + tr[rt].v;
  }

  void push_col(LL rt) {
    if (tr[rt].lazy) {
      LL l = tr[rt].l, r = tr[rt].r;
      if (l) {
        tr[l].lazy += tr[rt].lazy;
        tr[l].v += tr[rt].lazy;
        tr[l].sum += tr[l].cnt * tr[rt].lazy;
      }
      if (r) {
        tr[r].lazy += tr[rt].lazy;
        tr[r].v += tr[rt].lazy;
        tr[r].sum += tr[r].cnt * tr[rt].lazy;
      }
      tr[rt].lazy = 0;
    }
  }

  LL rebuild(LL l, LL r, LL dep) {  //重构
    if (l > r) return 0;
    D = dep;
    LL mid = (l + r) >> 1;
    nth_element(p + l, p + mid, p + r + 1);
    tr[mid] = p[mid];
    tr[mid].l = rebuild(l, mid - 1, (dep + 1) % dimension);
    tr[mid].r = rebuild(mid + 1, r, (dep + 1) % dimension);
    update(mid);
    return mid;
  }

  void checkSize() {
    if (cnt == block) {
      for (int i = 1; i <= cnt; i++) p[i] = tr[i];
      root = rebuild(1, cnt, 0);
      block += 10000;
    }
  }

  void ins(LL &rt, int d) {  //单点插入，如果没有就新开点
    if (!rt) {
      rt = ++cnt;
      for (int i = 0; i < dimension; i++)
        tr[rt].d[i] = tr[rt].maxpos[i] = tr[rt].minpos[i] = now.d[i];
      tr[rt].v = tr[rt].sum = now.v;
      return;
    }
    if (now == tr[rt]) {
      tr[rt].v += now.v, tr[rt].sum += now.v;
      return;
    }
    push_col(rt);
    if (now.d[d] < tr[rt].d[d])
      ins(tr[rt].l, d ^ 1);
    else
      ins(tr[rt].r, d ^ 1);
    update(rt);
  }

  LL query(LL rt, double x1, double y1, double x2, double y2) {
    if (!rt) return 0;
    LL res = 0;
    if (out(x1, y1, x2, y2, tr[rt].minpos[0], tr[rt].minpos[1],
            tr[rt].maxpos[0], tr[rt].maxpos[1]))
      return 0;
    if (in(x1, y1, x2, y2, tr[rt].minpos[0], tr[rt].minpos[1], tr[rt].maxpos[0],
           tr[rt].maxpos[1]))
      return tr[rt].sum;
    push_col(rt);
    if (in(x1, y1, x2, y2, tr[rt].d[0], tr[rt].d[1], tr[rt].d[0], tr[rt].d[1]))
      res += tr[rt].v;
    res += query(tr[rt].l, x1, y1, x2, y2) + query(tr[rt].r, x1, y1, x2, y2);
    update(rt);
    return res;
  }

  void modify(LL rt, double x1, double y1, double x2, double y2, LL add) {
    if (!rt) return;
    if (out(x1, y1, x2, y2, tr[rt].minpos[0], tr[rt].minpos[1],
            tr[rt].maxpos[0], tr[rt].maxpos[1]))
      return;
    if (in(x1, y1, x2, y2, tr[rt].minpos[0], tr[rt].minpos[1], tr[rt].maxpos[0],
           tr[rt].maxpos[1])) {
      tr[rt].lazy += add;
      tr[rt].sum += add * tr[rt].cnt;
      tr[rt].v += add;
      return;
    }
    push_col(rt);
    if (in(x1, y1, x2, y2, tr[rt].d[0], tr[rt].d[1], tr[rt].d[0], tr[rt].d[1]))
      tr[rt].v += add;
    modify(tr[rt].l, x1, y1, x2, y2, add);
    modify(tr[rt].r, x1, y1, x2, y2, add);
    update(rt);
  }

  void init() {
    root = cnt = 0;
    block = (LL)sqrt(N);
  }

  double getdis(const double val[dimension], LL rt) {  //估价函数，用来寻找区间
    double res = 0;
    for (LL i = 0; i < dimension; i++) {
      if (val[i] < tr[rt].minpos[i])
        res += (tr[rt].minpos[i] - val[i]) * (tr[rt].minpos[i] - val[i]);
      if (val[i] > tr[rt].maxpos[i])
        res += (val[i] - tr[rt].maxpos[i]) * (val[i] - tr[rt].maxpos[i]);
    }
    return res;
  }

  double ans = INF;

  void ask(double val[dimension], LL rt) {  //询问最近点
    double dis = 0;
    for (LL i = 0; i < dimension; i++)
      dis += ((tr[rt].d[i] - val[i]) * (tr[rt].d[i] - val[i]));
    if (dis == 0) dis = INF;
    if (dis < ans) ans = dis;
    double dl = tr[rt].l ? getdis(val, tr[rt].l) : INF;
    double dr = tr[rt].r ? getdis(val, tr[rt].r) : INF;
    if (dl < dr) {
      if (dl < ans) ask(val, tr[rt].l);
      if (dr < ans) ask(val, tr[rt].r);
    } else {
      if (dr < ans) ask(val, tr[rt].r);
      if (dl < ans) ask(val, tr[rt].l);
    }
  }
} Tree;

// KD树支持插入、查询最近点、坐标轴区间加和区间求和等
int n;
double xx, yy;

int main() {
  cin >> n;
  Tree.init();
  for (int i = 1; i <= n; i++) {
    cin >> xx >> yy;
    Node &now = Tree.now;
    now.d[0] = xx, now.d[1] = yy, now.v = 0, now.sum = 0;
    Tree.ins(Tree.root, 0);
    Tree.checkSize();
    Tree.ask(now.d, Tree.root);
  }
  cout << fixed << setprecision(4) << sqrt(Tree.ans) << endl;
}

珂朵莉树

在随机数据下表现较好

修改和查询操作都可以暴力执行

// build
struct Node {
  int l, r;
  mutable LL val;

  Node(int a = -1, int b = -1, LL c = 0) { l = a, r = b, val = c; }

  bool operator<(const Node &a) const { return l < a.l; }
};

set<Node> st;

// modify
set<Node>::iterator split(int pos) {
  auto it = st.lower_bound(Node(pos));
  if (it != st.end() && it->l == pos) return it;
  --it;
  Node tmp = *it;
  st.erase(it);
  st.insert(Node(tmp.l, pos - 1, tmp.val));
  return st.insert(Node(pos, tmp.r, tmp.val)).first;  // first return iterator
}

void assign(int l, int r, LL val) {
  auto itr = split(r + 1), itl = split(l);
  st.erase(itl, itr);
  st.insert((Node){l, r, val});
}

void add(int l, int r, LL val) {
  auto itr = split(r + 1), itl = split(l);
  for (auto it = itl; it != itr; ++it) it->val += val;
}

// query
LL querySum(int l, int r) {
  auto itr = split(r + 1), itl = split(l);
  LL res = 0;
  for (auto it = itl; it != itr; ++it) res += (it->r - it->l + 1) * it->val;
  return res;
}

LL queryKth(int l, int r, int k) {
  vector<pair<LL, int> > vec(0);
  auto itr = split(r + 1), itl = split(l);
  for (auto it = itl; it != itr; ++it)
    vec.emplace_back(it->val, it->r - it->l + 1);
  sort(vec.begin(), vec.end());
  for (vector<pair<LL, int> >::iterator it = vec.begin(); it != vec.end(); ++it)
    if ((k -= it->second) <= 0) return it->first;
  return -1;  // note:if there are negative numbers, return another impossible
              // number.
}

树套树思路

线段树套线段树: 维护多维信息，在没有要求强制在线时，可以用CDQ分治，整体二分处理
线段树套平衡树:【模板】二逼平衡树，维护区间内平衡树信息

关于树套树的构建，我们对于外层线段树正常建树，对于线段树上的某一个节点，建立一棵平衡树，包含该节点所覆盖的序列。具体操作时我们可以将序列元素一个个插入，每经过一个线段树节点，就将该元素加入到该节点的平衡树中。

操作一，求某区间中某值的排名：我们对于外层线段树正常操作，对于在某区间中的节点的平衡树，我们返回平衡树中比该值小的元素个数，合并区间时，我们将小的元素个数求和即可。最后将返回值+1，即为某值在某区间中的排名。

操作二，求某区间中排名为k的值：我们可以采用二分策略。因为一个元素可能存在多个，其排名为一区间，且有些元素原序列不存在。所以我们采取和操作一类似的思路，我们用小于该值的元素个数作为参考进行二分，即可得解。

操作三，将某个数替换为另外一个数：我们只要在所有包含某数的平衡树中删除某数，然后再插入另外一个数即可。外层依旧正常线段树操作。

操作四，求某区间中某值的前驱：我们对于外层线段树正常操作，对于在某区间中的节点的平衡树，我们返回某值在该平衡树中的前驱，线段树的区间结果合并时，我们取最大值即可。