算法数据结构

线段树大模板：区间修改(加法、乘法)、区间和查询

字数统计: 2.3k字   |   阅读时长: 11分
, ,

摘要: 线段树区间修改(加法、乘法)、区间和查询

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 线段树和树状数组：单点修改、区间和查询 中我们学习了线段树的单点更新、区间查询，并解决了区间求和的问题。

在文章 线段树：区间修改(更改为定值)、区间最值查询 中，我们处理了线段树区间更新，区间查询，并解决了区间最值问题。

本文我们还是解决区间求和问题，并且支持区间修改，修改方式上支持加法，乘法两种运算。线段树维护的思路与前面两篇文章差不多，我们大致复习一下要点，然后直接给出代码模板，这份模板跟之前两个的主要区别在于区间更新的方式是加法、乘法。

最后，我们用代码模板解决力扣 1622. 奇妙序列。

复习：线段树区间修改

懒标记

当线段树有区间修改的需求 range_update_add(i, j, delta) , range_update_mul(i, j, factor)时。

找到所有节点区间 [l, r] 包含在 [i, j] 内部的节点。找到这样的节点 tree[i] 后，不继续往下更新了，而是在该非叶节点的子节点上记录一下这个操作。

如果是加操作，将 delta 叠加在对应的懒标记上 lazy_add[2i+1] += delta, lazy_add[2i+2] += delta，如果是乘操作，将 factor 累乘在对应的懒标记上 lazy_mul[2i+1] *= factor, lazy_mul[2i+2] *= factor

被更新懒标记的这些子节点，用懒标记更新对应节点的时机就是查询和更新时搜索到对应区间的时候。

懒标记下传的时机是用懒标记更新对应节点之后。

懒标记更新时机

(1) 区间更新

当搜索到当前节点时，range_update_add(node, l, r, i, j, delta)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. 若当前节点的懒标记有内容则用该懒标记更新当前节点并下传
    用 lazy[node] 更新 tree[node] 
    若该节点不是叶节点，则将懒标记下传
    即更新 lazy[2 * node + 1] 和 lazy[2 * node + 2]
    删除懒标记， 即将 lazy[node] 置0
2. l > r || l > j || r < i，搜索区间[i, j]完全与节点区间[l, r]不重合
    直接返回
3. i <= l && r <= j，搜索区间完全把节点区间包含了
    用 delta 更新 tree[node]
    下传懒标记
4. 搜索区间与节点区间交叉，递归子节点，返回后合并结果
    range_update_add(2 * node + 1, l, mid, i, j, delta)
    range_update_add(2 * node + 2, mid + 1, r, i, j, delta)
    用 tree[2 * node + 1] 和 tree[2 * node + 2] 更新 tree[node]

(2) 区间查询

当搜索到当前节点时，range_query(node, l, r, i, j)：

1
2
3
4
5
6
7
8
9
10
11
12
13
1. l > r || l > j || r < i，搜索区间[i, j]完全与节点区间[l, r]不重合
    直接返回
2. 若当前节点的懒标记有内容，用该懒标记更新当前节点并下传(与更新是的操作相同)
    用 lazy[node] 更新 tree[node] 
    若该节点不是叶节点，则将懒标记下传
    即更新 lazy[2 * node + 1] 和 lazy[2 * node + 2]
    删除懒标记， 即将 lazy[node] 置0
3. i <= l && r <= j，搜索区间完全把节点区间包含了
    返回 tree[node]
3. 搜索区间与节点区间交叉，递归子节点，返回后合并结果
    ans_left = range_query(2 * node + 1, l, mid, i, j)
    ans_right = range_query(2 * node + 2, mid + 1, r, i, j)
    合并 ans_left 和 ans_right

带懒标记的线段树模板 (C++)

  • 更新支持：同时支持区间加法和区间乘法
  • 查询支持：区间和查询
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
using ll = long long;

class LazySegmentTree
{
public:
    LazySegmentTree(int n=0, int p=1e9+7)
    {
        this -> n = n;
        this -> MOD = p;
        tree.assign(n * 4, 0);
        lazy_add.assign(n * 4 , 0);
        lazy_mul.assign(n * 4, 1);
    }

    void range_update_add(int i, int j, int delta)
    {
        _range_update(0, 0, n, i, j, delta, 1);
    }

    void range_update_mul(int i, int j, int factor)
    {
        _range_update(0, 0, n, i, j, 0, factor);
    }

    int range_query(int i, int j)
    {
        return _range_query(0, 0, n, i, j);
    }

    int point_query(int i)
    {
        return _range_query(0, 0, n, i, i);
    }

    void point_update_add(int idx, int delta)
    {
        _range_update(0, 0, n, idx, idx, delta, 1);
    }

    void point_update_mul(int idx, int factor)
    {
        _range_update(0, 0, n, idx, idx, 0, factor);
    }

private:
    vector<int> tree;
    vector<int> lazy_add;
    vector<int> lazy_mul;
    int n;
    int MOD;

    void _range_update(int node, int l, int r, int i, int j, int delta, int factor)
    {
        if(lazy_add[node] != 0 || lazy_mul[node] != 1)
        {
            tree[node] = (tree[node] * (ll)lazy_mul[node] + (r - l + 1) * (ll)lazy_add[node]) % MOD;
            if(l != r)
            {
                lazy_mul[node * 2 + 1] = (lazy_mul[node * 2 + 1] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] + (ll)lazy_add[node]) % MOD;
                lazy_mul[node * 2 + 2] = (lazy_mul[node * 2 + 2] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] + (ll)lazy_add[node]) % MOD;
            }
            lazy_mul[node] = 1;
            lazy_add[node] = 0;
        }
        if(l > r || l > j || i > r)
            return;
        if(i <= l && j >= r)
        {
            tree[node] = (tree[node] * (ll)factor + (r - l + 1) * (ll)delta) % MOD;
            if(l != r)
            {
                lazy_mul[node * 2 + 1] = (lazy_mul[node * 2 + 1] * (ll)factor) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] * (ll)factor) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] + (ll)delta) % MOD;
                lazy_mul[node * 2 + 2] = (lazy_mul[node * 2 + 2] * (ll)factor) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] * (ll)factor) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] + (ll)delta) % MOD;
            }
            return;
        }
        int mid = (l + r) /2;
        _range_update(node * 2 + 1, l, mid, i, j, delta, factor);
        _range_update(node * 2 + 2, mid + 1, r, i, j, delta, factor);
        tree[node] = (tree[node * 2 + 1] + (ll)tree[node * 2 + 2]) % MOD;
    }

    int _range_query(int node, int l, int r, int i, int j)
    {
        if(l > r || l > j || r < i)
            return INT_MIN / 3;
        // 需要保证 lazy_add 和 lazy_mul 只有一个有内容
        if(lazy_add[node] != 0 || lazy_mul[node] != 1)
        {
            tree[node] = (tree[node] * (ll)lazy_mul[node] + (r - l + 1) * (ll)lazy_add[node]) % MOD;
            if(l != r)
            {
                lazy_mul[node * 2 + 1] = (lazy_mul[node * 2 + 1] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 1] = (lazy_add[node * 2 + 1] + (ll)lazy_add[node]) % MOD;
                lazy_mul[node * 2 + 2] = (lazy_mul[node * 2 + 2] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] * (ll)lazy_mul[node]) % MOD;
                lazy_add[node * 2 + 2] = (lazy_add[node * 2 + 2] + (ll)lazy_add[node]) % MOD;
            }
            lazy_mul[node] = 1;
            lazy_add[node] = 0;
        }
        if(i <= l && r <= j)
        {
            return tree[node];
        }
        int mid = (l + r) / 2;
        if(i > mid)
            return _range_query(node * 2 + 2, mid + 1, r, i, j);
        if(j <= mid)
            return _range_query(node * 2 + 1, l, mid, i, j);
        int ans_left = _range_query(node * 2 + 1, l, mid, i, j);
        int ans_right = _range_query(node * 2 + 2, mid + 1, r, i, j);
        int ans = 0;
        if(ans_left != INT_MIN / 3) ans = (ans + (ll)ans_left) % MOD;
        if(ans_right != INT_MIN / 3) ans = (ans + (ll)ans_right) % MOD;
        return ans;
    }
};

模板题

算法：线段树

修改：

  • 将某区间每一个数乘上 x。
  • 将某区间每一个数加上 x。

查询：

  • 求出某区间每一个数的和。

代码 (C++)

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
int main()
{
    int n, m, p;
    cin >> n >> m >> p;
    LazySegmentTree st(n + 1, p);
    for(int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        st.point_update_add(i, x);
    }
    for(int i = 0; i < m; ++i)
    {
        int op, x, y, k;
        cin >> op >> x >> y;
        if(op != 3)
            cin >> k;
        if(op == 1)
            st.range_update_mul(x, y, k);
        else if(op == 2)
            st.range_update_add(x, y, k);
        else
            cout << st.range_query(x, y) << endl;
    }
}

题目

1622. 奇妙序列

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类 ：

  • Fancy() 初始化一个空序列对象。
  • void append(val) 将整数 val 添加在序列末尾。
  • void addAll(inc) 将所有序列中的现有数值都增加 inc 。
  • void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
  • int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 1e9 + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

提示：

1
2
3
1 <= val, inc, m <= 100
0 <= idx <= 1e5
总共最多会有 1e5 次对 append，addAll，multAll 和 getIndex 的调用。

示例：
输入：
[“Fancy”, “append”, “addAll”, “append”, “multAll”, “getIndex”, “addAll”, “append”, “multAll”, “getIndex”, “getIndex”, “getIndex”]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]
解释：
Fancy fancy = new Fancy();
fancy.append(2); // 奇妙序列：[2]
fancy.addAll(3); // 奇妙序列：[2+3] -> [5]
fancy.append(7); // 奇妙序列：[5, 7]
fancy.multAll(2); // 奇妙序列：[52, 72] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3); // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10); // 奇妙序列：[13, 17, 10]
fancy.multAll(2); // 奇妙序列：[132, 172, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

算法：线段树

修改:

  • 区间加: range_update_add(l, r, delta)
  • 区间乘: range_update_mul(l, r, factor)

查询:

  • 单点查询: query(idx)，用查询区间和的方式实现。

代码 (C++)

在用懒标记更新 tree[node] 时，更新为 tree[node] * a + b，a 和 b 是懒标记记录的内容.

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
class Fancy {
public:
    Fancy() {
        st = LazySegmentTree(1e5 + 1);
        right = 0;
    }

    void append(int val) {
        st.point_update_add(right++, val);
    }

    void addAll(int inc) {
        st.range_update_add(0, right - 1, inc);
    }

    void multAll(int m) {
        st.range_update_mul(0, right - 1, m);
    }

    int getIndex(int idx) {
        if(idx >= right)
            return -1;
        return st.point_query(idx);
    }

private:
    LazySegmentTree st;
    int right;
};
Share