🎋 Hi from dodola

最近的笔记

线段树讲义||寒假

19分钟阅读

线段树介绍

  • 线段树是一棵二叉树，每个节点维护一个区间内的信息
  • 左子树区间维护的信息，右子树维护的信息
  • 节点信息可以由两个子节点合并得到
  • 任意一个区间会被分为线段树上个节点

线段树可以在的时间复杂度内实现单点修改、区间修改、**区间查询（区间求和/区间最大值/区间最小值）**等操作。

线段树一般解决类似这样的问题：

已知一个数列，你需要进行下面几种操作：

  1. 将某区间每一个数加上 。（修改）
  2. 求出某区间每一个数的和。（查询）
  3. 将某区间的每个数修改为。（修改）
  4. 求某区间的最大值/最小值。（查询）

建树

img

实现

递归实现

struct segTreeNode {
    ll d = 0ll, lazy = 0ll;     // 数据&懒标记
    bool used;  // 标记是否修改过
};
 
vector<ll>a(maxn);  // 原数据
vector<segTreeNode>tree(maxn * 4);
 
void build(int l, int r, int p) {
    if (l == r) {
        tree[p].d = a[l];
        return;
    }
    int m = l + ((r - l) >> 1);
 
    build(l, m, p << 1);	// 左边
    build(m + 1, r, (p << 1) | 1);	// 右边
 
    tree[p].d = tree[p << 1].d + tree[(p << 1) | 1].d;
}

查询&修改&求值

区间查询

进行区间查询的时候，区间和节点区间的关系有三种可能：

  1. 当前要查询的区间与正在询问的区间没有交集，返回空
  2. 当前要查询的区间被某个节点的区间完全包含，直接取该点记录的值
  3. 当前要查询的区间被某个节点部分包含，则将这个节点往下传递一层，直到符合上面两种情况

实现

ll getsum(int l, int r, int cl, int cr, int p) {
    // if (cr<l || cl>r)return 0ll;     // 操作正确的话不可能会出现这种情况
    if (cl >= l && cr <= r)return tree[p].d;
 
    int m = cl + ((cr - cl) >> 1);
    ll sum = 0ll;
    if (m >= l)
        sum += getsum(l, r, cl, m, p << 1);
    if (m < r)
        sum += getsum(l, r, m + 1, cr, (p << 1) | 1);
    return sum;
}

区间修改（懒标记）

区间修改和区间查询的思路是一样的，判断当前节点区间与被修改的区间的关系，对其数据进行修改。

假如我们在修改区间时，把所有与有交集的节点都遍历并修改一边，时间复杂度将过高，所以我们引入懒标记。

思考：

当我们要修改，有一个节点（或者是一些节点的并集）恰好是，我们选择节点数最少的那个集合进行修改，并对这些集合进行标记，只有当某次访问需要这些节点的子节点时，才把变化传递下去，这样可以大大减少对更深处的节点的修改次数，降低时间复杂度。

实现

void update(int l, int r, int cl, int cr, int p, ll x) {
    // 给区间[l,r]的每个数都加上x
    // if (cr<l || cl>r)return;
    if (cl >= l && cr <= r) {
        tree[p].d += (cr - cl + 1) * x;
        tree[p].lazy += x;
        return;
    }
    int m = cl + ((cr - cl) >> 1);
    if (tree[p].lazy) {
        tree[p << 1].d += tree[p].lazy * (m - cl + 1);
        tree[(p << 1) | 1].d += tree[p].lazy * (cr - m);
        tree[p << 1].lazy += tree[p].lazy;
        tree[(p << 1) | 1].lazy += tree[p].lazy;
        tree[p].lazy = 0ll;
    }
    if (m >= l)update(l, r, cl, m, p << 1, x);
    if (m < r)update(l, r, m + 1, cr, (p << 1) | 1, x);
 
    tree[p].d = tree[p << 1].d + tree[(p << 1) | 1].d;
}

相应的，引入懒区间之后，我们在区间查询的时候要考虑懒标记是否下达，如果没有下达则要将懒标记传递下去。

ll getsum(int l, int r, int cl, int cr, int p) {
    // if (cr<l || cl>r)return 0ll;     // 操作正确的话不可能会出现这种情况
    if (cl >= l && cr <= r)return tree[p].d;
 
    int m = cl + ((cr - cl) >> 1);
 
    if (tree[p].lazy) {
        tree[p << 1].lazy += tree[p].lazy, tree[(p << 1) | 1].lazy += tree[p].lazy;
        tree[p << 1].d += tree[p].lazy * (m + 1 - cl), tree[(p << 1) | 1].d += tree[p].lazy * (cr - m);
        tree[p].lazy = 0;
    }
 
    ll sum = 0ll;
    if (m >= l)
        sum += getsum(l, r, cl, m, p << 1);
    if (m < r)
        sum += getsum(l, r, m + 1, cr, (p << 1) | 1);
    return sum;
}

例题指路：

区间求和：P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

参考

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
/*
线段树模板1：实现区间加/求和的模板
洛谷P3372
*/
struct segTreeNode {
    ll d, lazy;     // 数据&懒标记
    bool used;  // 标记是否修改过
};
 
vector<ll>a(maxn);  // 原数据
vector<segTreeNode>tree(maxn * 4);
 
void build(int l, int r, int p) {
    if (l == r) {
        tree[p].d = a[l];
        return;
    }
    int m = l + ((r - l) >> 1);
 
    build(l, m, p << 1);
    build(m + 1, r, (p << 1) | 1);
 
    tree[p].d = tree[p << 1].d + tree[(p << 1) | 1].d;
}
 
void update(int l, int r, int cl, int cr, int p, ll x) {
    // 给区间[l,r]的每个数都加上x
    // if (cr<l || cl>r)return;
    if (cl >= l && cr <= r) {
        tree[p].d += (cr - cl + 1) * x;
        tree[p].lazy += x;
        return;
    }
    int m = cl + ((cr - cl) >> 1);
    if (tree[p].lazy) {
        tree[p << 1].d += tree[p].lazy * (m - cl + 1);
        tree[(p << 1) | 1].d += tree[p].lazy * (cr - m);
        tree[p << 1].lazy += tree[p].lazy;
        tree[(p << 1) | 1].lazy += tree[p].lazy;
        tree[p].lazy = 0ll;
    }
    if (m >= l)update(l, r, cl, m, p << 1, x);
    if (m < r)update(l, r, m + 1, cr, (p << 1) | 1, x);
 
    tree[p].d = tree[p << 1].d + tree[(p << 1) | 1].d;
}
 
ll getsum(int l, int r, int cl, int cr, int p) {
    // if (cr<l || cl>r)return 0ll;     // 操作正确的话不可能会出现这种情况
    if (cl >= l && cr <= r)return tree[p].d;
 
    int m = cl + ((cr - cl) >> 1);
    if (tree[p].lazy) {
        tree[p << 1].lazy += tree[p].lazy, tree[(p << 1) | 1].lazy += tree[p].lazy;
        tree[p << 1].d += tree[p].lazy * (m + 1 - cl), tree[(p << 1) | 1].d += tree[p].lazy * (cr - m);
        tree[p].lazy = 0;
    }
    ll sum = 0ll;
    if (m >= l)
        sum += getsum(l, r, cl, m, p << 1);
    if (m < r)
        sum += getsum(l, r, m + 1, cr, (p << 1) | 1);
    return sum;
}
 
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    build(1, n, 1);
    while (m--) {
        int op;cin >> op;
        if (op == 1) {
            int x, y;ll k;
            cin >> x >> y >> k;
            update(x, y, 1, n, 1, k);
        }
        else {
            int x, y;cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << '\n';
        }
    }
}
 
int main() {
    int _ = 1;
    // cin >> _;cin.get();
    while (_--)
        solve();
}

思考

相似的，如果是将某个区间内的值都修改为某个值，应该如何操作？

例题 1（两种懒标记）

P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

操作 1： 格式：1 x y k 含义：将区间内每个数乘上 k

操作 2： 格式：2 x y k 含义：将区间 内每个数加上 k

操作 3： 格式：3 x y 含义：输出区间 内每个数的和对 m 取模所得的结果

这题需要考虑两种修改值的操作之间的相互影响。

  • 每次对节点加/乘之前，要判断是否需要将当前节点的两种懒标记向下传递
  • 判断时应该先乘后加

参考

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
/*
线段树模板2：实现区间加+乘、求和的模板
洛谷P3372
*/
struct segTreeNode {
    ll d, lazyPlus, lazyTime;
    /*TIP:在开结构体vector时已有初始值会使所有初始值塞入程序，会导致编译时间过长+内存溢出*/
    bool used;  // 标记是否修改过
};
 
ll mo;
vector<ll>a(maxn);  // 原数据
vector<segTreeNode>tree(maxn * 4);
 
void build(int l, int r, int p) {
    tree[p].lazyTime = 1ll;
    if (l == r) {
        tree[p].d = a[l] % mo;
        return;
    }
    int mid = l + ((r - l) >> 1);
 
    build(l, mid, p << 1);
    build(mid + 1, r, (p << 1) | 1);
 
    tree[p].d = (tree[p << 1].d + tree[(p << 1) | 1].d) % mo;
}
 
void pd(int cl, int cr, int p) {
    int l = p << 1;
    int r = (p << 1) | 1;
    // 先乘后加
    if (tree[p].lazyTime != 1ll) {
        tree[l].lazyTime *= tree[p].lazyTime;
        tree[r].lazyTime *= tree[p].lazyTime;
        tree[l].lazyTime %= mo;
        tree[r].lazyTime %= mo;
 
        // 对子节点懒标记乘
        tree[l].lazyPlus *= tree[p].lazyTime;
        tree[r].lazyPlus *= tree[p].lazyTime;
        tree[l].lazyPlus %= mo;
        tree[r].lazyPlus %= mo;
        // 对子节点数值乘
        tree[l].d *= tree[p].lazyTime;
        tree[r].d *= tree[p].lazyTime;
        tree[l].d %= mo;
        tree[r].d %= mo;
 
        tree[p].lazyTime = 1ll;
    }
 
    int mid = cl + ((cr - cl) >> 1);
 
    if (tree[p].lazyPlus) {
        tree[l].d += tree[p].lazyPlus * (mid - cl + 1);
        tree[l].d %= mo;
        tree[r].d += tree[p].lazyPlus * (cr - mid);
        tree[r].d %= mo;
        tree[l].lazyPlus += tree[p].lazyPlus;
        tree[l].lazyPlus %= mo;
        tree[r].lazyPlus += tree[p].lazyPlus;
        tree[r].lazyPlus %= mo;
        tree[p].lazyPlus = 0ll;
    }
}
 
void updateTime(int l, int r, int cl, int cr, int p, ll x) {
    // 给区间[l,r]的每个数都乘上x
    if (cl >= l && cr <= r) {
        tree[p].lazyTime *= x;
        tree[p].lazyTime %= mo;
        tree[p].lazyPlus *= x;
        tree[p].lazyPlus %= mo;
        tree[p].d *= x;
        tree[p].d %= mo;
        return;
    }
 
    pd(cl, cr, p);
 
    int mid = cl + ((cr - cl) >> 1);
    if (mid >= l)updateTime(l, r, cl, mid, p << 1, x);
    if (mid < r)updateTime(l, r, mid + 1, cr, (p << 1) | 1, x);
 
    tree[p].d = (tree[p << 1].d + tree[(p << 1) | 1].d) % mo;
}
 
void updatePlus(int l, int r, int cl, int cr, int p, ll x) {
    // 给区间[l,r]的每个数都加上x
    if (cl >= l && cr <= r) {
        tree[p].d += (cr - cl + 1) * x;
        tree[p].d %= mo;
        tree[p].lazyPlus += x;
        tree[p].lazyPlus %= mo;
        return;
    }
 
    pd(cl, cr, p);
 
    int mid = cl + ((cr - cl) >> 1);
    if (mid >= l)updatePlus(l, r, cl, mid, p << 1, x);
    if (mid < r)updatePlus(l, r, mid + 1, cr, (p << 1) | 1, x);
 
    tree[p].d = (tree[p << 1].d + tree[(p << 1) | 1].d) % mo;
}
 
ll getsum(int l, int r, int cl, int cr, int p) {
    if (cl >= l && cr <= r)return tree[p].d;
 
    int mid = cl + ((cr - cl) >> 1);
 
    pd(cl, cr, p);
 
    ll sum = 0ll;
    if (mid >= l)
        sum += getsum(l, r, cl, mid, p << 1);
    sum %= mo;
    if (mid < r)
        sum += getsum(l, r, mid + 1, cr, (p << 1) | 1);
    return sum % mo;
}
 
void solve() {
    int n, q;cin >> n >> q >> mo;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    build(1, n, 1);
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x, y;ll k;
            cin >> x >> y >> k;
            updateTime(x, y, 1, n, 1, k);
        }
        else if (op == 2) {
            int x, y;ll k;
            cin >> x >> y >> k;
            updatePlus(x, y, 1, n, 1, k);
        }
        else {
            int x, y;cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << '\n';
        }
    }
}
 
int main() {
    int _ = 1;
    // cin >> _;cin.get();
    while (_--)
        solve();
}

动态开点

一般来说，线段树处理的范围在，一般是的大小。

如果我们想处理负数的范围，或者是达到的数量级时，我们就需要可以动态开点的线段树。

线段树我们一般开到的大小是充足的，为了节省空间以及直接建立全树的时间，我们也可以对线段树动态开点，也就是只有当我们需要用到某些节点的时候，才去创造它。

比如，我们已经一个节点表示的相关数据，我们需要修改上的信息，我们就创造和的节点，并继续递归创建节点，直到这个线段树可以完全表示到已被修改的信息。

实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxv = 8e6;  // 一般有多大开多大
 
/*
线段树模板3：动态开点技巧
*/
struct segTreeNode {
    ll d, lazy;
    int lson, rson; // 记录左右子的下标
};
 
vector<segTreeNode>tree(maxv);
int tot = 1;    // 总节点数
 
void update(int cl, int cr, int& p, ll addnum) {
    if (!p)p = ++tot;
    tree[p].d += addnum * (cr - cl + 1);
    tree[p].lazy += addnum;
}
 
void pushdown(int p, int cl, int cr) {  // 节点p没有左右子时给它开点。
    if (cr - cl + 1 <= 1)return;
    int mid = (cr + cl - 1) >> 1;
    update(cl, mid, tree[p].lson, tree[p].lazy);
    update(mid + 1, cr, tree[p].rson, tree[p].lazy);
    tree[p].lazy = 0;
}
 
void updatePlus(int l, int r, int cl, int cr, int p, ll x) {
    // 给区间[l,r]里每个数加x
    if (cl >= l && cr <= r) {
        tree[p].d += x * (cr - cl + 1);
        tree[p].lazy += x;
        return;
    }
    pushdown(p, cl, cr);
    int mid = (cl + cr - 1) >> 1;
    if (mid >= l)updatePlus(l, r, cl, mid, tree[p].lson, x);
    if (mid < r)updatePlus(l, r, mid + 1, cr, tree[p].rson, x);
 
    int ls = tree[p].lson, rs = tree[p].rs;
    tree[p].d = tree[ls].d + tree[rs].d;
}
 
ll getsum(int l, int r, int cl, int cr, int p) {
    if (cl >= l && cr <= r)return tree[p].d;
 
    pushdown(p, cl, cr);
    int mid = (cl + cr - 1) / 2;  // 可以处理区间两端是负数的情况
    ll sum = 0ll;
    sum += getsum(l, r, cl, mid, tree[p].lson);
    sum += getsum(l, r, mid + 1, cr, tree[p].rson);
    return sum;
}
 
void solve() {
    ll n, q;cin >> n >> q;
    while (q--) {
        ll l, r, k;cin >> l >> r >> k;
        if(k==1){}
    }
}
 
int main() {
    int _ = 1;
    // cin >> _;cin.get();
    while (_--)
        solve();
}

线段树合并与分裂

线段树合并

线段树合并通过递归实现，需要有合并操作的线段树需要使用动态开点的技巧。

将线段树 a 和 b 合并，从 1 号点开始递归，若递归到某个节点为空，直接返回另一个树上的对应节点；若递归到叶子节点，我们合并两棵树上的对应节点。

void pushup(int a) {
    int ls = tree[a].lson, rs = tree[a].rson;
    tree[a].d = tree[ls].d + tree[rs].d;
}
 
int merge(int a, int b, int l, int r) {
    if (!a)return b;
    if (!b)return a;
    if (l == r) {
        // do sth
        return a;
    }
 
    int mid = (l + r) >> 1;
    tree[a].lson = merge(tree[a].lson, tree[b].lson, l, mid);
    tree[a].rson = merge(tree[a].rson, tree[b].rson, mid + 1, r);
 
    pushup(a);
    return a;
}

模板题：[P4556 Vani 有约会] 雨天的尾巴 /【模板】线段树合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树分裂

线段树分裂是线段树合并的逆过程。

线段树分裂只适用于有序的序列，无序的序列是没有意义的，常用在动态开点的权值线段树上。

当分裂和合并都存在时，要注意回收节点，以免分裂时会出现节点重复/占用的问题。

  1. 当与有交集时开新节点
  2. 当包含于时，直接将当前节点接到新的树下面，把旧边断开。
void pushup(int a) {
    int ls = tree[a].lson, rs = tree[a].rson;
    tree[a].d = tree[ls].d + tree[rs].d;
}
 
void split(int& p, int& q, int s, int t, int l, int r) {
    // 从[s,t]的线段树中分裂出区间是[l,r]的线段树
    if (t < l || r < s) return;
    if (!p) return;
    if (l <= s && t <= r) {
        q = p;
        p = 0;
        return;
    }
    if (!q) q = ++tot;
    int m = s + t >> 1;
    if (l <= m) split(tree[p].lson, tree[p].rson, s, m, l, r);
    if (m < r) split(tree[p].lson, tree[p].rson, m + 1, t, l, r);
    pushup(p);
    pushup(q);
}

模板题：P5494 【模板】线段树分裂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

练习题一览

一些模板题/测测你的板子(!

P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Problem - 5306 (hdu.edu.cn)

[P4556 Vani 有约会] 雨天的尾巴 /【模板】线段树合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P5494 【模板】线段树分裂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[P4097 【模板】李超线段树 / HEOI2013] Segment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3391 【模板】文艺平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

关系图谱