常见的数据结构梳理

线段树

复习了一会线段树， 觉得线段树最精妙的地方就在于 lazyTag 表达的含义

lazyTag 打的标记是该节点的所有子节点， 不包括自己

分析更新的正确性， 对于当前节点， 执行完 push_down 操作后， 可以保证其左右孩子上的 sum 值都是正确的

所以最后一句 sum[o] = sum[lo] + sum[ro] 的正确性可以保障

void updt(const int& L,const int& R,const int64_t& val, int o = 1,int l = 1,int r = n){
    if(L <= l and r <= R){
        sum[o] += (r - l + 1) * val;
        lz[o] += val;
        return;
    }
    push_down(o, l, r);
    if(L <= mid) updt(L, R, val, lo, l, mid);
    if(R > mid) updt(L, R, val, ro, mid + 1, r);
    sum[o] = sum[lo] + sum[ro];
}

考虑进行更新时经过的节点， 对于每一层， 最多只会经过两个节点， 因此复杂度是 (log n)

树状数组

树状数组的英文名是 Binary Indexed Trees

对于 C[i] ， 它维护的是一个以 i 结尾， 长度为 lowbit(i) 的区间和， 如上图所示

查询 [1, x] 的区间和， 其实就是对 x 进行了一个从后往前的二进制拆分， 因为维护的是类似后缀的东西，

显然 S[1,x] = C[x] + C[x - lowbit(x)] , 不停的跳即可

对于一个单点的更新操作， 每次向上跳 lowbit ， 可以保证是最小且有效的步数

void add(int pos,int val){
    for(;pos <= n;pos += -pos & pos) C[pos] += val;
}
int query(int p){
    int ans = 0;
    for(;p;p -= -pos & pos) ans += C[p];
    return ans;
}

树状数组也可以用来区间加减，区间查询

设 (A_i) 是原数组， (d_i = A_i - A_{i-1}) 是 (A) 的差分数组

有

[S_n = sum_{i=1}^nA_i = d_1 + \d_1 + d_2 +\ d_1 + d_2 + d_3 + \ ... \d_1 + d_2 + d_3 + d_4 + ... + d_n \ = n (d_1 + d_2 + ... + d_n) - sum_{i=1}^nd_i(i-1) ]

设 (B_i = d_i(i-1))

则

[S_n = nsum d - sum B ]

而当一段区间 ([L,R]) 一起加上 (x) 的时候，

对于 (d) 来说，只有 (d_L) 和 (d_{R+1}) 发生了变化

对于 (B) 来说，也是同理，所以可以开两个树状数组来进行维护

struct{
	  ll C[N][2]; // 0 是差分d_i , 1 是 d_i * (i - 1)
	  void add(int pos, ll val, int o) {
	  	  for (; pos <= n; pos += (-pos) & pos) C[pos][o] += val;
	  }
	  ll ask(int pos, int o) {
	  	  ll ans = 0;
	  	  for (; pos; pos -= (-pos) & pos) ans += C[pos][o];
	  	  return ans;
	  }

	  void updt(int l, int r, int x) {
	  	  add(l, x, 0); add(r + 1, -x, 0);
	  	  add(l, x * (l - 1), 1); add(r + 1, -x * (r), 1);
	  }
	  ll query(int l, int r) {
	  	  ll R = r * ask(r, 0) - ask(r, 1);
	  	  ll L = (l - 1) * ask(l - 1, 0) - ask(l - 1, 1);
	  	  return R - L;
	  }
}BIT;

主席树

其实就是一个桶， 挂链的时候复制链的信息动态开点，查询区间 k 大的时候，对两棵树进行查询即可

挂链可以挂成线性的可以挂成树形

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

const int maxn = 5e5 + 10;

int sum[maxn << 5], L[maxn << 5], R[maxn << 5];
int cnt;

int a[maxn], id[maxn], root[maxn];

int build(int l, int r) {
    int rt = ++cnt;
    sum[rt] = 0;
    if (l < r) {
        L[rt] = build(l, mid);
        R[rt] = build(mid + 1, r);
    }
    return rt;
}

int updt(int pre, int l, int r, int pos) {
    int rt = ++cnt;
    sum[rt] = sum[pre] + 1;

    R[rt] = R[pre];
    L[rt] = L[pre];

    if (l < r) {
        if (pos <= mid) {
            L[rt] = updt(L[pre], l, mid, pos);
        }
        else {
            R[rt] = updt(R[pre], mid + 1, r, pos);
        }
    }
    return rt;
}

int queryK(int x, int y, int l, int r, int k) {
    if (l == r) {
        return r;
    }
    int num = sum[L[y]] - sum[L[x]];
    if (num >= k) {
        return queryK(L[x], L[y], l, mid, k);
    }
    else {
        return queryK(R[x], R[y], mid + 1, r, k - num);
    }
}