线段树

普通线段树

区间合并

单点修改和查询区间内最大的连续子段和（有负数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int n, m;
int a[MAXN];
struct segmentnode {
    int l, r;
    ll sum, lmx, rmx, mx; //mx表示最大区间和，lsum表示最大前缀和，rsum表示最大后缀和
} tree[MAXN << 2];

void pushup(int rt) {
    int suml = tree[rt << 1].mx;
    int sum = tree[rt << 1].rmx + tree[rt << 1 | 1].lmx;
    int sumr = tree[rt << 1 | 1].mx;
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
    tree[rt].mx = max({suml, sum, sumr});
    tree[rt].lmx = max(tree[rt << 1].lmx, tree[rt << 1].sum + tree[rt << 1 | 1].lmx);
    tree[rt].rmx = max(tree[rt << 1 | 1].rmx, tree[rt << 1 | 1].sum + tree[rt << 1].rmx);
}

void build(int rt, int l, int r) {
    tree[rt].l = l, tree[rt].r = r;
    if (l == r) {
        tree[rt].sum = a[l];
        tree[rt].mx = a[l];
        tree[rt].lmx = a[l], tree[rt].rmx = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

segmentnode query(int rt, int l, int r) {
    if (tree[rt].l >= l && tree[rt].r <= r)
        return tree[rt];
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if (mid >= r)
        return query(rt << 1, l, r);
    else if (mid + 1 <= l)
        return query(rt << 1 | 1, l, r);
    else {
        auto left = query(rt << 1, l, r);
        auto right = query(rt << 1 | 1, l, r);
        segmentnode ans;
        ans.sum = left.sum + right.sum;
        ans.lmx = max(left.lmx, left.sum + right.lmx);
        ans.rmx = max(right.rmx, right.sum + left.rmx);
        ans.mx = max({left.mx, right.mx, left.rmx + right.lmx});
        return ans;
    }
}

void update(int rt, int pos, ll x) {
    if (tree[rt].l == tree[rt].r && pos == tree[rt].l) {
        tree[rt].sum = x;
        tree[rt].mx = x;
        tree[rt].lmx = x, tree[rt].rmx = x;
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (pos <= mid)
        update(rt << 1, pos, x);
    else if (pos > mid)
        update(rt << 1 | 1, pos, x);
    pushup(rt);
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    build(1, 1, n);
    while (m--) {
        int opt, x, y;
        opt = read(), x = read(), y = read();
        if (opt == 1) {
            //查询 
            if (x > y) swap(x, y);
            printf("%lld\n", query(1, x, y).mx);
        }
        else if (opt == 2) //修改
            update(1, x, y);
    }
}

懒惰节点的熟练应用（区间加+区间乘两种懒惰标记）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
ll a[MAXN];
ll n, m, mod;
ll opt, l, r, x, y;
struct node {
    int l, r, len;
    ll sum;
    ll add, mul; //懒惰标记
} tree[MAXN << 2];

void work(node &now, ll c, ll d) {
    //c(ax+b)+d 
    now.sum = (now.sum * c + now.len * d) % mod;
    now.mul = (now.mul * c) % mod;
    now.add = (now.add * c + d) % mod;
}

void pushup(int rt) {
    tree[rt].sum = (tree[rt << 1].sum + tree[rt << 1 | 1].sum) % mod;
}

void pushdown(int rt) {
    work(tree[rt << 1], tree[rt].mul, tree[rt].add);
    work(tree[rt << 1 | 1], tree[rt].mul, tree[rt].add);
    tree[rt].add = 0;
    tree[rt].mul = 1;
}

void build(int rt, int l, int r) {
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].len = r - l + 1;
    tree[rt].add = 0, tree[rt].mul = 1;
    if (l == r) {
        tree[rt].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, ll c, ll d) {
    //c表示乘，d表示加 
    if (tree[rt].l >= l && tree[rt].r <= r) {
        work(tree[rt], c, d);
        return;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l)
        update(rt << 1, l, r, c, d);
    if (mid + 1 <= r)
        update(rt << 1 | 1, l, r, c, d);
    pushup(rt);
}

ll query(int rt, int l, int r) {
    if (tree[rt].l >= l && tree[rt].r <= r) {
        return tree[rt].sum;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    ll ans = 0;
    if (mid >= l)
        ans = (ans + query(rt << 1, l, r)) % mod;
    if (mid + 1 <= r)
        ans = (ans + query(rt << 1 | 1, l, r)) % mod;
    return ans;
}

void solve() {
    n = read(), mod = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    build(1, 1, n);
    m = read();
    while (m--) {
        opt = read();
        if (opt == 1) {
            //multiply
            l = read(), r = read(), x = read();
            update(1, l, r, x, 0);
        }
        else if (opt == 2) {
            l = read(), r = read(), x = read();
            update(1, l, r, 1, x);
        }
        else {
            l = read(), r = read();
            printf("%lld\n", query(1, l, r));
        }
    }
}

动态开点

建立一颗 "残疾"的线段树，上面只有询问过的相关节点，从而节省了大量空间，让值域特别大的权值线段树的方案可行。

原版线段树是一颗完整的二叉树，所以可以采取计算的方法求出左右儿子的编号。可是动态开点法不一样，因为这是一颗残疾的树，此时这种计算方法根本无效，所以左右儿子节点必须人为规定。

具体实现方法就是，如果当前的节点还未被使用过（rtrt == 0），那么就把 ++ idxidx 赋给这个点。与此同时，由于是递归回溯结构，所以这个时候该点的左儿子编号和右儿子编号都已经确定过了。

几个注意点：idxidx 初值赋为 11，给根节点预留出来；动态开点结构体存的是左右儿子的编号不是区间信息，区间信息通过传参引入；updateupdate 时 rtrt 必须加上取址符，因为这个传进来的 rtrt 需要变化。

空间复杂度：O(qlogN)O(qlogN) ，时间复杂度：O(qlogN)O(qlogN)

以求逆序对为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int n, idx = 1, rt = 1; //idx必须设为1
int LL = 1, RR = 1000000000; //值域
struct node {
    int l, r; //左右儿子的编号
    ll cnt;
}tree[MAXN * 27];

void pushup (int rt) {tree[rt].cnt = tree[tree[rt].l].cnt + tree[tree[rt].r].cnt;}

void update(int &rt, int L, int R, ll val, ll y) {
    //别忘了加取址符
    if (!rt)
        rt = ++idx;
    if (L == R) {
        tree[rt].cnt += y;
        return;
    }
    ll mid = L + R >> 1;
    if (val <= mid) update(tree[rt].l, L, mid, val, y);
    else update(tree[rt].r, mid + 1, R, val, y);
    pushup(rt);
}

ll query(int rt, int L, int R, int l, int r) {
    if (L >= l && R <= r) return tree[rt].cnt;
    int mid = L + R >> 1;
    ll ans = 0;
    if (mid + 1 <= r) ans += query(tree[rt].r, mid + 1, R, l, r);
    if (l <= mid) ans += query(tree[rt].l, L, mid, l, r);
    return ans;
}

void solve() {
    n = read();
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int num = read();
        ans += query(rt, LL, RR, num + 1, RR);
        update(rt, LL, RR, num, 1);
    }
    printf("%lld\n", ans);
}

权值线段树

定义

权值线段树是线段树的一个扩展，但是不同于普通线段树，它维护的是值域。

举个例子，对于一个给定的数组，普通线段树可能维护的是某个子数组的和，而权值线段树可以维护某个区间内数组元素出现的次数。

在实现上，由于值域范围通常较大，权值线段树一般采用 离线+离散化+堆式存储 或者 动态开点+链式存储的策略来优化空间。单次操作的时间复杂度为 O(logn)O(logn)。

权值线段树的节点用来表示一个区间的数出现的次数，以下图为例

存储结构

堆式存储：rt, rt << 1 | 1, rt << 1,

链式存储: struct node {int cnt, l, r}，l和r不再存放区间的范围而是左儿子和右儿子的下标

基本作用

查询第 kk 小或第 kk 大

查询某个数的排名

查询比某个数小的最大值，查询比某个数大的最小值

堆式存储（常规线段树）模板（以普通平衡树为例题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
int n; //节点个数
vector <int> num; //离散化后的数据
int opt[MAXN], a[MAXN]; //离线存储操作
struct node {
    // 基于二叉堆建树，而非指针 
    int l, r, cnt; //值域[l,r](离散化后)里出现了cnt个数, l,r表示区间中的理论最值
}tree[MAXN << 2];

void pushup(int rt)  {
    tree[rt].cnt = tree[rt << 1].cnt + tree[rt << 1 | 1].cnt;
}

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

void update(int rt, int x, int y) {
    //插入或删除一个值为x的数
    if(tree[rt].l == tree[rt].r) {
        tree[rt].cnt += y;
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (x <= mid) update(rt << 1, x, y);
    if (mid + 1 <= x) update(rt << 1 | 1, x, y);
    pushup(rt);
}

int getrank(int rt, int x) {
    //查询值为x的数的排名，实则查询[1,x-1]已出现的数字的个数，相当于区间查询
    if (tree[rt].r < x) return tree[rt].cnt;
    int mid = tree[rt].l + tree[rt].r >> 1;
    int ans = getrank(rt << 1, x); //左边肯定有贡献，因为会取到最小值
    if (x > mid + 1) ans += getrank(rt << 1 | 1, x);
    return ans;
}

int kth(int rt, int k) {
    //查询排名为k的数的大小
    if (tree[rt].l == tree[rt].r) {
        return tree[rt].l;
    }
    if (tree[rt << 1].cnt >= k) return kth(rt << 1, k); 
    else return kth(rt << 1 | 1, k - tree[rt << 1].cnt); //注意减去左子树的大小
}

int findmx(int rt) {
    //区间中的实际最大值
    if (tree[rt].l == tree[rt].r) return tree[rt].r;
    if (tree[rt << 1 | 1].cnt) return findmx(rt << 1 | 1); //右子树中还有数
    else return findmx(rt << 1);
}

int findpre(int rt, int x) {
    //查找最大的比x小的数是多少
    if (tree[rt].r < x) {
        if (tree[rt].cnt) return findmx(rt);
        else return 0;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (x > mid + 1 && tree[rt << 1 | 1].cnt) {
        int ans = findpre(rt << 1 | 1, x); //按照值来看在右子树中
        if (ans) return ans; //右子树中不存在这个节点
    }
    return findpre(rt << 1, x); //在右子树找不到只能去左子树找
}

int findmn(int rt) {
    //区间中的实际最小值
    if (tree[rt].l == tree[rt].r) return tree[rt].l;
    if (tree[rt << 1].cnt) return findmn(rt << 1);
    else return findmn(rt << 1 | 1);
}

int findnxt(int rt,int x) {
    //查找最小的比x大的数
    if (tree[rt].l > x) {
        if(tree[rt].cnt) return findmn(rt);
        else return 0;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (x < mid && tree[rt << 1].cnt) {
        int ans = findnxt(rt << 1, x);
        if (ans) return ans;
    }
    return findnxt(rt << 1 | 1, x);
}

int findx(int x) {
    return lower_bound(num.begin(), num.end(), x) - num.begin();
}

void solve() {
    n = read();
    num.pb(-1e8);
    for (int i = 1; i <= n; i++) {
        opt[i] = read();
        a[i] = read();
        if (opt[i] != 4) //离线操作插入所有数字，4是查询排名没有出现可能未知的数字
            num.pb(a[i]);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    int siz = num.size(); //一共出现了多少数字
    build(1, 1, siz);
    for (int i = 1; i <= n; i++) {
        int t = opt[i];
        if (t == 1) //插入x
            update(1, findx(a[i]), 1);
        else if (t == 2) //删除x
            update(1, findx(a[i]), -1);
        else if (t == 3) //查询x的排名
            printf("%d\n", getrank(1, findx(a[i])) + 1);
        else if (t == 4) //查询排名为x的数
            printf("%d\n", num[kth(1, a[i])]);
        else if (t == 5) //查询小于x的最大的数
            printf("%d\n", num[findpre(1, findx(a[i]))]);
        else if (t == 6) //查询大于x的最小的数
            printf("%d\n", num[findnxt(1, findx(a[i]))]);
    }

}

int main() {
    solve();
    return 0;
}

动态开点初始建树时，只建根节点，然后将各个节点逐一插入。

具体的，当修改函数要修改一个不存在的节点时，就新建一个节点，用 idxidx 来实现赋予下标的操作

在动态开点过程中，存储必须以结构体形式。因为动态开点的下标是人为规定的，并且不是按满二叉树的形式存储。由于涉及到更改一个节点左右儿子的编号值，传节点编号时必须传引用。同时，由于权值线段树维护值域而不是区间范围的特殊之处，根节点无法像往常一样在 buildbuild 函数中完成建立，所以必须预留一个空位置给根节点，也就是 idxidx 从 11 开始。

链式存储（动态开点）模板，以普通平衡树为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
int n;
#define base 10000001 //本题特殊，有负数，加上这个数是为了保证非负
#define LL 1 //区间范围下限
#define RR 20000001 //区间范围上限
int idx = 1; //用于权值线段树动态开点，必须预留一个位置给根节点
struct node {
    //存放的l和r是左右子树的下标而非区间的范围
    int l, r, cnt; // cnt表示当前区间的数字出现的次数
}tree[MAXN << 2];

void pushup(int rt) {
    tree[rt].cnt = tree[tree[rt].l].cnt + tree[tree[rt].r].cnt;
}

void update(int &rt, int L, int R, int val, int y) {
    //L,R表示区间信息，一定要加引用
    if (!rt) {
        rt = ++ idx; 
        tree[rt] = {0, 0, 0};
    }
    if (L == R) {
        tree[rt].cnt += y;
        if (tree[rt].cnt < 0) tree[rt].cnt = 0;
        return;
    }
    int mid = L + R >> 1;
    if (val <= mid) update(tree[rt].l, L, mid, val, y);
    if (mid + 1 <= val) update(tree[rt].r, mid + 1, R, val, y);
    pushup(rt);
}

int query(int rt, int L, int R, int l, int r) {
    //L,R表示区间信息，查询x的排名是多少
    if (!rt) return 0;
    if (L >= l && R <= r) return tree[rt].cnt;
    int mid = L + R >> 1;
    int ans = 0;
    if (l <= mid) ans += query(tree[rt].l, L, mid, l, r);
    if (mid + 1 <= r) ans += query(tree[rt].r, mid + 1, R, l, r);
    return ans;
}

int kth(int rt, int L, int R, int k) {
    //查询第k小的数是什么
    if (L == R) return L;
    int mid = L + R >> 1;
    if (tree[tree[rt].l].cnt >= k) return kth(tree[rt].l, L, mid, k);
    else return kth(tree[rt].r, mid + 1, R, k - tree[tree[rt].l].cnt);
}

int getpre(int rt, int x) {
    //查找小于x的最大值 
    int rk = query(1, LL, RR, LL, x - 1 + base);
    return kth(1, LL, RR, rk) - base;
}

int getnxt(int rt, int x) {
    //查找大于x的最小值
    int rk = query(1, LL, RR, LL, x + base) + 1;
    return kth(1, LL, RR, rk) - base;
}

void solve() {
    n = read();
    //输入有负数的存在
    for (int i = 1; i <= n; i++) {
        int opt, x;
        opt = read(), x = read();
        int rt = 1;
        if (opt == 1) // 插入一个数
            update(rt, LL, RR, x + base, 1);         
        else if (opt == 2) //删除一个数
            update(rt, LL, RR, x + base, -1);          
        else if (opt == 3) //查询数值为x的数的排名
            printf("%d\n", query(1, LL, RR, LL, base + x - 1) + 1);
        else if (opt == 4) //查询排名为x的数的数值大小
            printf("%d\n", kth(1, LL, RR, x) - base);
        else if (opt == 5) //查找小于x的最大数
            printf("%d\n", getpre(1, x));
        else if (opt == 6) //查找大于x的最小数
            printf("%d\n", getnxt(1, x));
    }
}

吉司机线段树（势能线段树）

介绍

传统的区间修改是通过 lazylazy 标记来规避掉大规模的单点修改来节省时间。若要使用 lazylazy 标记，需要满足以下条件

  • 区间节点的值可以利用 lazylazy 标记来更新
  • 多次 lazylazy 标记可以快速合并

比如区间求和，当前节点的值可以通过 lazylazy 乘区间长度来更新，lazylazy 标记的值也可以快速加减。

但是对于区间开根号，区间位运算来说，区间节点的值不能利用 lazylazy 标记来计算，就不能实现传统的 lazylazy 合并和区间更新，只能对所有叶子节点进行单独修改。

但是仔细观察可以发现，这些操作对每个节点的操作次数是有一个隐含的上限的，就像一个固定的势能，只要超过这个上限值，相应的操作变回退化失效，即势能为00 。而当势能为 00 的节点组成区间时，这个区间上的所有 updateupdate 操作就可以一并规避掉。并且通常情况下，势能的下降是非常迅速的。具体做法就是

  • 用势能函数替代 lazylazy 节点，记录和维护当前区间节点的势能值
  • 对于每次的区间修改，若当前区间的势能值为 00 ，则直接规避掉
  • 若存在势能值不为 00 的节点，继续向下递归到叶子节点或者满足上一点。

时间复杂度不超过 O(log2N)O(log^2N)

代码模板1,区间开方求区间和

以区间开方求区间和为例，规定势能函数节点范围内最大的值。若势能值为 11 ，就可以规避掉所有的区间修改操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
ll n;
ll a[MAXN];
struct node {
    int l, r;
    ll sum;
    ll mxopt; //传说中的势能函数
}tree[MAXN << 2];

void pushup(int rt) {
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
    tree[rt].mxopt = max(tree[rt << 1].mxopt, tree[rt << 1 | 1].mxopt); //更新势能函数
}

void build(int rt, int l, int r) {
    tree[rt].l = l, tree[rt].r = r;
    if (l == r) {
        tree[rt].sum = a[l];
        tree[rt].mxopt = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r) {
    if (tree[rt].l == tree[rt].r) {
        //看似是单点更新，但根据更新上限小的特点时间复杂度说得过去
        tree[rt].sum = (ll)(sqrt(tree[rt].sum));
        tree[rt].mxopt = (ll)(sqrt(tree[rt].mxopt));
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l && tree[rt << 1].mxopt > 1) update(rt << 1, l, r);
    if (mid + 1 <= r && tree[rt << 1 | 1].mxopt > 1) update(rt << 1 | 1, l, r);
    pushup(rt);
}

ll query(int rt, int l, int r) {
    if (tree[rt].l >= l && tree[rt].r <= r) return tree[rt].sum;
    ll ans = 0;
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l) ans += query(rt << 1, l, r);
    if (mid + 1 <= r) ans += query(rt << 1 | 1, l, r);
    return ans;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    build(1, 1, n);
    int m;
    m = read();
    while (m--) {
        int opt, l, r;
        opt = read(), l = read(), r = read();
        if (l > r) swap(l, r);
        if (opt == 0) update(1, l, r); //区间开方
        else printf("%lld\n", query(1, l, r)); //区间求和
    }
}

代码模板2，区间与运算求区间最大值

区间与运算求区间最大值。三个操作，区间内所有数与一个数，改变一个数，求区间最值。可以很直观的把二进制下 11 的个数当做势能函数，若势能值为 00 就规避，但这样常数太大还是会被卡。

实际上可以利用与运算不会多产生 11 的性质。区间最大值改变有两种情况，原先的最大值变小了或者产生了一个新的最大值。在区间与运算框架下只可能是前者。所以，只有当区间里的值在运算后有可能变小后才进行区间修改操作。

规定势能函数为节点范围内所有值的或，当势能值与运算给定值后势能值会变小才进行区间修改操作。否则就相当于区间内的所有数都不会变小，也就是当前的最大值不可能变小，就没必要进行区间修改操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int n, m;
int a[MAXN];
struct node {
    int l, r;
    int mxopt;
    int mx;
}tree[MAXN << 2];

void pushup(int rt) {
    tree[rt].mxopt = tree[rt << 1].mxopt | tree[rt << 1 | 1].mxopt;
    tree[rt].mx = max(tree[rt << 1].mx, tree[rt << 1 | 1].mx); 
}

void build(int rt, int l, int r) {
    tree[rt].l = l, tree[rt].r = r;
    if (l == r) {
        tree[rt].mxopt = a[l];
        tree[rt].mx = a[l];
        return;
    } 
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int k) {
    if (tree[rt].l == tree[rt].r) {
        tree[rt].mx = tree[rt].mx & k;
        tree[rt].mxopt = tree[rt].mxopt & k;
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l && (tree[rt << 1].mxopt & k) < tree[rt << 1].mxopt) 
        update(rt << 1, l, r, k);
    if (mid + 1 <= r && (tree[rt << 1 | 1].mxopt & k) < tree[rt << 1 | 1].mxopt) 		
        update(rt << 1 | 1, l, r, k);
    pushup(rt);
}

void change(int rt, int pos, int k) {
    if (tree[rt].l == tree[rt].r && tree[rt].l == pos) {
        tree[rt].mx = k;
        tree[rt].mxopt = k;
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (pos <= mid) change(rt << 1, pos, k);
    if (mid + 1 <= pos) change(rt << 1 | 1, pos, k);
    pushup(rt);
}

int query(int rt, int l, int r) {
    if (tree[rt].l >= l && tree[rt].r <= r) return tree[rt].mx;
    int ans = 0;
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l) ans = query(rt << 1, l, r);
    if (mid + 1 <= r) ans = max(ans, query(rt << 1 | 1, l, r));
    return ans;
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    build(1, 1, n);
    char s[10];
    int l, r;
    int k;
    while (m--) {
        scanf("%s", s);
        l = read(), r = read();
        if (s[0] == 'A') {
            //区间与运算
            k = read();
            update(1, l, r, k);
        }
        else if (s[0] == 'U') {
            //改变某一个位置的值
            change(1, l, r);
        }
        else //区间求最大值
            printf("%d\n", query(1, l, r));
    }
}

扫描线

二维平面有 nn 个平行于坐标轴的矩形，现在要求出这些矩形的面积并。

由于 yy 可能取浮点数，所以要对所有的 y1,y2,...y2ny_1, y_2, ... y_{2n} 提前读入离散化去重后存储。也就是说，这些 yy 其实是端点的编号，访问真实值需要通过这些编号去 vectorvector 提取。

定义扫描线为输入给出的矩形的所有横向边。整个过程按照纵坐标从小到大的顺序依次通过这些线段对整个区间进行扫描，顾名思义扫描线。

模拟一下整个过程，应该还是比较清晰的：

扫到 11 时，B,CB,C 区间出现，面积贡献不变

扫到 22 时，A,BA,B 区间出现，同时 BB 区间的贡献增加 lenB×dx1len_B \times dx_1 ，CC 区间的贡献增加 lenC×dx1len_C \times dx_1

扫到 33 时，B,CB,C 区间出现次数减 11 ，AA 区间的贡献增加 lenA×dx2len_A \times dx_2 ，BB 区间的贡献增加 lenB×dx2len_B \times dx_2 ，CC 区间的贡献增加 lenC×dx2len_C \times dx_2 。 CC 区间消失。

扫到 44 时，类似于前面的过程，A,BA,B 区间算上各自对面积的贡献后消失，程序结束。

由此可以看到，对于每条扫描线，我们需要记录下他的左右端点，纵坐标大小以及其贡献是正还是负。读入所有扫描线后按照纵坐标大小将其排序然后顺次枚举。定义扫描线个数为cnt。

定义被覆盖的区间总长为len。

面积就是 ∑1cnt−1dx×len\sum_1^{cnt-1}{dx \times len} ，这段区间总长用线段树求解。

线段树叶子节点存储的是原子区间信息（是区间不是节点），l和rl和r 表示左右子区间的序号，cntcnt 表示该段区间出现的次数，lenlen 表示该段区间真正的长度。

线段树维护的根本信息就是 cntcnt 和 lenlen 。

结论（不会证明）：扫描线问题中区间修改不需要 pushdownpushdown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
int n; //矩形个数
struct segment {
    //扫描线信息
    double x, y1, y2;
    int k; //区分一个矩形中的两个线段
}seg[MAXN << 1]; //MAXN 表示矩形个数，乘以2才表示线段
bool cmp(segment a, segment b) {
    return a.x < b.x;
}
struct node {
    //线段树节点表示的是区间不是节点
    int l, r, cnt; //cnt表示该段区间出现的次数，l和r表示左右两个子区间的序号
    double len; //线段真正的长度，而非 r - l + 1，公式下面会推
}tree[MAXN << 3]; //一共有2n个区间所以要再乘以2

vector <double> ys; //去重离散化，存放所有横坐标上点的位置，为了线段树的区间操作做准备
int findx(double x) {return lower_bound(ys.begin(), ys.end(), x) - ys.begin();}

void pushup(int rt) {
    //假设左区间的编号 = 0,右区间的编号 = 1;
    //y[0]为ys[0]到ys[1]的距离,表示0号区间的长度; y[1]为ys[1]到ys[2]的距离，表示1号区间的长度
    //当前区间的长度为 y[0]+y[1]=ys[1]-ys[0]+ys[2]-ys[1]=ys[2]-ys[0]
    //结论：tree[rt].len = ys[tree[rt].r + 1] - ys[tree[rt].l]
    if (tree[rt].cnt) tree[rt].len = ys[tree[rt].r + 1] - ys[tree[rt].l]; //整个区间都被覆盖
    else if (tree[rt].l != tree[rt].r) tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;
    else tree[rt].len = 0; //叶子节点且未被覆盖
}

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

void update(int rt, int l, int r, int k) {
    //l点到r点的出现次数+1
    if (tree[rt].l >= l && tree[rt].r <= r) {
        tree[rt].cnt += k;
        pushup(rt); //更新len
        return;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l) update(rt << 1, l, r, k);
    if (mid + 1 <= r) update(rt << 1 | 1, l, r, k);
    pushup(rt);
}

void solve() {
    // n = read();
    ys.clear(); //多组测试数据清空数据
    for (int i = 1, j = 0; i <= n; i++) {
        double x1, x2, y1, y2;
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        seg[++j] = {x1, y1, y2, 1};
        seg[++j] = {x2, y1, y2, -1};
        ys.pb(y1), ys.pb(y2);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end()); //离散化去重
    sort(seg + 1, seg + 1 + 2 * n, cmp); //将线段按纵坐标排序

    // 去重后y轴上一共有siz个节点，siz - 1个区间，对这些区间建树
    int siz = ys.size();
    build(1, 0, siz - 2);
    double ans = 0;
    for (int i = 1; i <= 2 * n; i ++) {
        //扫描线扫过去
        if (i > 1) ans += tree[1].len * (seg[i].x - seg[i - 1].x);
        update(1, findx(seg[i].y1), findx(seg[i].y2) - 1, seg[i].k);

    }
    printf("%.2lf\n", ans);
}

主席树（可持久化权值线段树）

概述

就像可持久化 01trie01trie ，为了实现可持久化，就要保存线段树的历史版本。通过观察不难发现，每次进行 单点修改 时，发生变化的只有从根节点到叶子节点这一条链上的节点。也就是说，只有lognlogn 个节点发生了变化，而其他的节点都可以重用，所以就有了如下的思路：

每次修改（或插入），新建一个根节点，并且向下递归需要新建的节点。

以求区间第 kk 小值为例题。已知利用权值线段树可以求出整个区间的第 kk 小数，可以利用可持久化权值线段树分别求得 [1,l−1][1,l-1] 和 [1,r][1,r] 的前缀和。前者可以求出插入 l−1l-1 个数，也就是第 l−1l-1 个版本下区间的第 kk 小值，后者同理。他们的差就是这中间插入的数的总和，利用这个总和就可以求得区间 kk 小值。如果左子树的数量大于等于 kk， 就递归访问左子树，否则就递归访问右子树。

对于动态开点，类似于可持久化 01trie01trie

  • 与上一版本没差异的地方直接复制节点编号
  • 有差异，裂开（在这个版本号下递归生成一条链）

时间复杂度 O(nlog2n)O(nlog_2n) ，空间复杂度O(4n+nlog2n)O(4n+nlog_2n)，一般开MAXN << 5就没啥问题

模板，求区间k小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
vector <int> num; //离散化用
int findx(int x) {return lower_bound(num.begin(), num.end(), x) - num.begin() + 1;} //离散化用
int n, m; //n个数据, m组询问
int a[MAXN]; //存放原始数据和离散化后结果
int rt[MAXN], idx; //不同的版本入口
struct node {
    int l, r, cnt;
}tree[(MAXN << 2) + MAXN * 17]; //空间复杂度 O(原本size + nlog2n)

int build(int l, int r) {
    int now = ++idx;
    int mid = l + r >> 1;
    if (l < r) {
        tree[now].l = build(l, mid);
        tree[now].r = build(mid + 1, r);
    }
    tree[now].cnt = 0;
    return now;
}

int update(int pre, int L, int R, int k) {   
    //上一个版本变化的部分全部裂开成一条新的链，其他不变的继承上一个版本
    int now = ++idx;
    int mid = L + R >> 1;
    tree[now].l = tree[pre].l, tree[now].r = tree[pre].r, tree[now].cnt = tree[pre].cnt + 1;//继承
    if (L < R) {
        if (k <= mid) tree[now].l = update(tree[pre].l, L, mid, k); //裂开
        else if (mid + 1 <= k) tree[now].r = update(tree[pre].r, mid + 1, R, k); //裂开
    }
    return now;
}

int query(int l, int r, int L, int R, int k) {
    //sum[r] - sum[l] 即为区间第k大值
    if (L == R) return L; //找到了这个数
    int mid = L + R >> 1;
    int sum = tree[tree[r].l].cnt - tree[tree[l].l].cnt; //这段区间的左部分插入了sum个数
    if (sum >= k) 
        return query(tree[l].l, tree[r].l, L, mid, k);
    else 
        return query(tree[l].r, tree[r].r, mid + 1, R, k - sum);
}

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read(),num.pb(a[i]);
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    for (int i = 1 ; i <= n; i++)
        a[i] = findx(a[i]);
    int len = num.size();
    rt[0] = build(1, len);
    for (int i = 1; i <= n; i++)
        rt[i] = update(rt[i-1], 1, len, a[i]);
    while (m--) {
        //询问[l,r]这个区间的第k小数
        int l, r, k;
        l = read(), r = read(), k = read();
        int ans = query(rt[l - 1], rt[r], 1, len, k);
        printf("%d\n", num[ans - 1]);
    }
}

平衡树（treap实现）

顾名思义，treap=tree+heaptreap = tree + heap ，其中 treetree 指的是二叉搜索树，heapheap 指的是大根堆。这种数据结构要求每个节点拥有两种权值，其中一种满足二叉搜索树的性质，另外一种满足大根堆的性质。这样做是为了让整个二叉搜索树尽可能随机，防止二叉搜索树向链的方向演变。

众所周知，一个序列对应有好几种二叉搜索树，然而这些搜索树时间复杂度差异甚大。treaptreap 无法将时间复杂度降到最优，但是通过随机的演变可以避免最坏情况的发生。具体的实现就是通过引入另一权值，为了让这个权值满足大根堆的性质（这个值是随机取的），随机的左旋右旋转转当前的搜索树。这样，利用堆，二叉搜索树的不稳定性就被人为锁死了。

先放两张左旋和右旋的图以免自己猪脑过载。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
int n; //节点数量
int opt, x;
int root, idx; //有些操作要引用，定义root；idx就相当于链表操作
struct node {
    //存放平衡树中的节点信息
    int l, r, cnt; //左右儿子编号，当前数出现次数
    int key, val; //BST和大根堆的权值
    int size; //子树大小
}tree[MAXN];

void pushup(int rt) {
    //维护size
    tree[rt].size = tree[tree[rt].l].size + tree[tree[rt].r].size + tree[rt].cnt;
}

int new_node(int key) {
    //新建一个节点，相当于new一个指针
    int now = ++idx;
    tree[now] = {0, 0, 1, key, rand(), 1};
    return idx;
}

void zag(int &p) {
    //左旋
    int q = tree[p].r;
    tree[p].r = tree[q].l, tree[q].l = p, p = q;
    pushup(tree[p].l), pushup(p);
}

void zig(int &p) {
    //右旋
    int q = tree[p].l;
    tree[p].l = tree[q].r, tree[q].r = p, p = q;
    pushup(tree[p].r), pushup(p); 
}

void build() {
    //加两个哨兵，正无穷和负无穷防止越界
    new_node(-INF), new_node(INF);
    root = 1, tree[1].r = 2;
    pushup(root);
    if (tree[1].val < tree[2].val) zag(root); //满足堆的性质，旋转
}

void insert(int &now, int key) {
    //插入一个值为key的值，因为涉及到根的修改所以加个引用
    if (!now) now = new_node(key); //走到叶子节点就新建一个
    else {
        if (key == tree[now].key) tree[now].cnt ++; //找到了相同的节点
        else if (key < tree[now].key) {
            insert(tree[now].l, key);
            if (tree[tree[now].l].val > tree[now].val) zig(now);
        } 
        else if (key > tree[now].key) {
            insert(tree[now].r, key);
            if (tree[tree[now].r].val > tree[now].val) zag(now); 
        }
    }
    pushup(now); //别忘了更新size
}

void remove(int &now, int key) {
    //删除一个值为key的值，因为涉及到根的修改所以加个引用
    if (!now) return; //要删除的节点不存在，直接退出
    if (tree[now].key == key) {
        if (tree[now].cnt > 1) tree[now].cnt --;
        else {
            //这个点直接没了 
            if (tree[now].l || tree[now].r) {
                //判断是不是叶子节点
                if (!tree[now].r && tree[tree[now].l].val) {
                    zig(now);
                    remove(tree[now].r, key);
                }
                else {
                    zag(now);
                    remove(tree[now].l, key);
                }
            }
            else now = 0; //叶子节点不用转来转去直接删
        }
    }
    else if (key > tree[now].key) remove(tree[now].r, key);
    else remove(tree[now].l, key);
    pushup(now); //别忘了更新size
}

int getrank(int rt, int key) {
    //查询值为x的排名
    if (!rt) return 0;
    if (key == tree[rt].key) return tree[tree[rt].l].size + 1;
    else if (key < tree[rt].key) return getrank(tree[rt].l, key);
    else return getrank(tree[rt].r, key) + tree[tree[rt].l].size + tree[rt].cnt;
}

int kth(int rt, int k) {
    //查询第k大的数
    if (!rt) return INF;
    if (tree[tree[rt].l].size >= k) return kth(tree[rt].l, k);
    else if (tree[tree[rt].l].size + tree[rt].cnt >= k) return tree[rt].key;
    else return kth(tree[rt].r, k - tree[tree[rt].l].size - tree[rt].cnt);
}

int getpre(int rt, int key) {
    //查找小于key的最大数
    if (!rt) return -INF;
    if (key <= tree[rt].key) return getpre(tree[rt].l, key);
    else return max(tree[rt].key, getpre(tree[rt].r, key));
}

int getnxt(int rt, int key) {
    //查找大于key的最小数
    if (!rt) return INF;
    if (key >= tree[rt].key) return getnxt(tree[rt].r, key);
    else return min(tree[rt].key, getnxt(tree[rt].l, key));
}

void solve() {
    n = read();
    build(); //别忘了建树
    for (int i = 1; i <= n; i++) {
        opt = read(), x = read();
        if (opt == 1) //插入一个数
            insert(root, x);
        else if (opt == 2) //删除一个数
            remove(root, x);
        else if (opt == 3) //查询一个数的排名
            printf("%d\n", getrank(root, x) - 1); //减一是因为插入了一个负无穷大的哨兵
        else if (opt == 4) //查询第k大的数
            printf("%d\n", kth(root, x + 1)); //同样是因为负无穷大的哨兵
        else if (opt == 5) //查询小于x的最大数
            printf("%d\n", getpre(root, x));
        else if (opt == 6) //查询大于x的最小数
            printf("%d\n", getnxt(root, x));
    }
}

树链剖分

概述

通过一些操作，将树转化成一个序列，把树中的任意一条路径对应到 O(logn)O(logn) 段的连续区间，然后用其他的数据结构维护区间信息。

定义

重/轻儿子：当前节点的子节点中子树 sizesize 最大的子节点称为该点的重儿子，其余都为轻儿子。

重/轻边：当前节点到重儿子的边称为重边，到轻儿子的边称为轻边

重链：由重边构成的极大路径

image-20220717201115059

其中红色节点为重儿子，红色边为重边，框起来的是重链，显然轻儿子是重链的顶点。

dfsdfs 序：优先遍历重儿子，即可保证重链上所有点的编号是连续的

结论：树中任意一条路径均可拆分为 O(logn)O(logn) 个连续区间/重链

具体转化方法

类似于求 LCALCA 的思想，通过重链往上爬，找到最近公共重链，每爬一次就修改一次。最后到达公共重链以后，再把公共重链给修改一次。

image-20220717201124262

两趟 dfsdfs ，第一趟预处理所有节点的重儿子，子树的 sizesize ，所有节点的深度，以及所有节点的父节点。

第二趟找到每个节点所属重链的顶点，dfsdfs 序的编号，建立从本身 idid 到 dfsdfs 序的映射，以及映射意义下所有点的权值（用于建线段树）

修改查询区间信息时间复杂度为 O(logn)O(logn) ，一共有 lognlogn 个区间，所以处理一次询问的时间复杂度是 O(log2n)O(log^2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
int n;
int siz[MAXN], son[MAXN], fa[MAXN], depth[MAXN], top[MAXN]; //son表示重儿子,fa表示父节点，top表示重链顶端
int key[MAXN], val[MAXN], a[MAXN], cnt;//key表示映射关系val表示映射关系意义下的权值
int head[MAXN];int tot;
struct EDGE {
    int to,next;
}edge[MAXM];
void add_edge(int from,int to) {
    edge[++tot].to=to;edge[tot].next=head[from];head[from]=tot;
}
struct node {
    int l, r, len;
    ll add, sum;
}tree[MAXN << 2];

void dfs1(int now,int dep, int pre) {
    //得到以当前节点为根的子树大小，当前节点的父节点，当前节点的深度，当前节点的重儿子
    depth[now] = dep, fa[now] = pre, siz[now] = 1;
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == pre) continue;
        dfs1(to, dep + 1, now);
        siz[now] += siz[to];
        if (siz[to] > siz[son[now]])
            son[now] = to;
    }
}

void dfs2(int now,int boss) {
    //按照dfs序给每个节点编号为之后的区间处理做准备
    key[now] = ++ cnt, a[cnt] = val[now], top[now] = boss;
    if (!son[now]) return;
    dfs2(son[now], boss);
    for (int i = head[now]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (to == fa[now] || to == son[now]) continue;
        dfs2(to, to);
    } 
}

void pushup(int rt) {
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}

void work(node &rt, ll add) {
    rt.sum += rt.len * add;
    rt.add += add;
}

void pushdown(int rt) {
    work(tree[rt << 1], tree[rt].add);
    work(tree[rt << 1 | 1], tree[rt].add);
    tree[rt].add = 0;
}

void build(int rt, int l, int r) {
    tree[rt] = {l, r, r - l + 1, 0, a[l]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int add) {
    if (tree[rt].l >= l && tree[rt].r <= r) {
        work(tree[rt], add);
        return;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if (mid >= l) update(rt << 1, l, r, add);
    if (mid + 1 <= r) update(rt << 1 | 1, l, r, add);
    pushup(rt);
}

ll query(int rt, int l, int r) {
    if (tree[rt].l >= l && tree[rt].r <= r) {
        return tree[rt].sum;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    ll ans = 0;
    if (mid >= l) ans += query(rt << 1, l, r);
    if (mid + 1 <= r) ans += query (rt << 1 | 1, l, r);
    return ans;
}

void update_tree(int rt, int add) {
    update(1, key[rt], key[rt] + siz[rt] - 1, add);
}

ll query_tree (int rt) {
    return query(1, key[rt], key[rt] + siz[rt] - 1);
}

void update_path(int u, int v, int add) {
    while (top[u] != top[v]) {
        //寻找最近公共重链 
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        update(1, key[top[u]], key[u], add);
        u = fa[top[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    update(1, key[v], key[u], add); //公共重链上别忘了更新区间信息
}

ll query_path(int u, int v) {
    ll ans = 0;
    while (top[u] != top[v]) {
        //寻找最近公共重链 
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ans += query(1, key[top[u]], key[u]);
        u = fa[top[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    ans += query(1, key[v], key[u]); //公共重链上别忘了计算区间贡献
    return ans;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) val[i] = read();
    for (int i = 1; i < n; i++) {
        int u, v;
        u = read(), v = read();
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs1(1, 1, -1);
    dfs2(1, 1);
    build(1, 1, n);
    int k;
    k = read();
    for (int i = 1; i <= k; i++) {
        int opt;
        int u, v, add;
        opt = read(), u = read();
        if (opt == 1) {
            //修改路径节点权值
            v = read(), add = read();
            update_path(u, v, add);
        }
        else if (opt == 2) {
            //修改子树节点权值
            add = read();
            update_tree(u, add);
        }
        else if(opt == 3) {
            //查询路径节点权值和
            v = read();
            printf("%lld\n", query_path(u, v));
        }
        else //查询子树节点权值和
            printf("%lld\n", query_tree(u));
    }
}

分块

分块是一种思想，一种非常优美的暴力做法。

大体思路就是把一个数组分成若干块（一般来说都是 n\sqrt{n} ），这样段的长度和个数都是 n\sqrt{n} 。以线段树模板区间修改（加上某个数）和区间求和为例。这样每次查询或修改时就可以将区间分成两部分，个数 ≤n\leq \sqrt{n} 的完整段和长度 ≤2n\leq 2\sqrt{n} 的两个部分段。这样操作可以分为两部分，一部分对完整段，一部分对操作区间内的残缺段。

image-20220717201135067

这样每一段就都可以看成一个节点（就像线段树的节点一样）。为了保证效率与准确性需要记录以下信息：

  • addadd ：类似于懒惰标记，本段中的所有数都要加上 addadd 的值，但是不会下推
  • sumsum ：本段的真实和是多少（加上懒惰标记后的值）

然后修改操作，时间复杂度O(n)O(\sqrt{n})

image-20220717201145693

查询操作，时间复杂度 O(n)O(\sqrt{n})

image-20220717201154873

思维难度 时间复杂度 代码难度
分块 easyeasy n\sqrt{n} ，但常数小 长度适中易调试
线段树 hardhard lognlogn ，常数大 长又难调试
树状数组 hardhard lognlogn 最短但难理解

以区间加和区间求和为例题，代码这样写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
ll add[320], sum[320]; //懒惰标记和区间和的真实值
int n, m; //区间长度和操作个数
char opt[10]; 
int a[MAXN]; 
int l, r, d;
int len; //块的长度

int get(int x) {
    //通过点编号获得块编号
    return (x - 1) / len;
}

void update(int l, int r, int d) {
    if (get(l) == get(r)) {
        //段内直接暴力 
        for (int i = l; i <= r; i ++) a[i] += d, sum[get(i)] += d;
    }
    else {
        int i = l, j = r;
        while (get(i) == get(l)) sum[get(i)] += d, a[i] += d, i ++;
        while (get(j) == get(r)) sum[get(j)] += d, a[j] += d, j --;
        for (int k = get(i); k <= get(j); k ++) sum[k] += d * len, add[k] += d;
    }
}

ll query(int l, int r) {
    ll ans = 0;
    if (get(l) == get(r)) {
        //段内直接暴力
        for (int i = l; i <= r; i ++) ans += a[i] + add[get(i)];
    }
    else {
        int i = l, j = r;
        while (get(i) == get(l)) ans += a[i] + add[get(i)], i ++;
        while (get(j) == get(r)) ans += a[j] + add[get(j)], j --;
        for (int k = get(i); k <= get(j); k ++) ans += sum[k];
    }
    return ans;
}

void solve() {
    n = read(), m = read();
    len = sqrt(n); //分块
    for (int i = 1; i <= n; i ++) a[i] = read(), sum[get(i)] += a[i];
    while (m--) {
        scanf("%s%d%d",opt, &l, &r);
        if (opt[0] == 'C') {
            d = read();
            update(l, r, d);
        }
        else
            printf("%lld\n", query(l, r));
    }
}

int main() {
    solve();
    return 0;
}

莫队

莫队算法可以理解成对 双指针处理离线询问的一种优化。精髓就是用较为合理的对询问进行排序，然后基于这个较优的询问顺序暴力回答每个询问。这也是双指针的核心，处理完一个询问后，可以用它的信息得到下一个询问区间的答案。

给出一组数据，可以看看莫队和普通排序访问有什么不同

(1,99999)(2,2)(3,99999)(4,4)(5,99999)(6,6)...(m/2−1,99999),(m/2,m/2)(1, 99999) (2, 2)(3,99999)(4,4)(5,99999)(6,6)...(m/2-1,99999),(m/2,m/2)

莫队提供了这样一种排序方案：将原序列以 n\sqrt{n} 为一块进行分块（当然大小可以调整），排序第一关键字是询问的左端点所在块的编号，第二关键字是询问的右端点本身的位置，都是升序。

这样所有的询问就被分成了 n\sqrt{n} 块，块的长度为 n\sqrt{n} ，块内部所有点的右端点都是递增的。

这样右端点的总数在每一块内走的总数 ≤n\leq n ，一共有 n\sqrt{n} 块，所以右端点走的次数不超过 nnn\sqrt{n} 次。时间复杂度 O(nn)O(n\sqrt{n})

左端点块内移动不超过 n\sqrt{n} ，一共有 mm 个询问，总共不超过 mnm\sqrt{n} ；块间移动不超过 2n2\sqrt{n} ，块间移动的次数不超过 n−1\sqrt{n} - 1 ，时间复杂度不超过 2n2n 。时间复杂度O(mn)O(m\sqrt{n})

由于出题人过于毒瘤，有一种较为常见的玄学优化。奇数块块内右端点从小到大，偶数块右端点从大到小排。

只写了最基础的莫队，以求区间内有多少个不同的数为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define get(x) (x / len)
using namespace std;
const int N = 5e4 + 5, M = 2e5 + 5, S = 1e6 + 5;
int n, m, a[N], ans[M], cnt[S], len;
struct Query {
    int id, l, r;
} q[M];
bool cmp(Query a, Query b) {
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}
void add(int x, int &res) {
    if (!cnt[x]) res ++;
    cnt[x] ++;
}
void del(int x, int &res) {
    cnt[x] --;
    if (!cnt[x]) res --;
}
signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    scanf("%d", &m);
    len = sqrt((double)n * n / m);
    for (int i = 0; i < m; i ++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q, q + m, cmp);
    for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++) {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) add(a[++ i], res);
        while (i > r) del(a[i --], res);
        while (j > l) add(a[-- j], res);
        while (j < l) del(a[j ++], res);
        ans[id] = res;
    }
    for (int i = 0; i < m; i ++) 			printf("%d\n", ans[i]);
}