首页 程序设计 数据结构

# 01 区间，区间取反，区间求和

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
struct SegTree {
private:
    int n;                  // 原始数组长度
    int size;               // 线段树大小（2的幂次）
    vector<int> tree;       // 线段树，存储区间中1的个数
    vector<int> lazy;       // 懒标记：0-不取反，1-需要取反

    // 构建线段树
    void build(const vector<int>& data) {
        for (int i = 0; i < n; i++) {
            tree[size + i] = data[i + 1];  // data是1-based，但线段树底层用0-based索引
        }
        for (int i = size - 1; i >= 1; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    // 对节点应用取反操作
    void apply(int idx, int l, int r) {
        // 取反后，1的个数变为区间长度减去原来的1的个数
        tree[idx] = (r - l + 1) - tree[idx];
        lazy[idx] ^= 1;  // 翻转懒标记
    }

    // 下推懒标记
    void push(int idx, int l, int r) {
        if (lazy[idx] != 0) {
            int mid = (l + r) / 2;
            apply(2 * idx, l, mid);
            apply(2 * idx + 1, mid + 1, r);
            lazy[idx] = 0;
        }
    }

    // 区间取反更新（递归函数）
    void update(int l, int r, int idx, int segL, int segR) {
        if (r < segL || l > segR) {
            return;
        }

        if (l <= segL && segR <= r) {
            apply(idx, segL, segR);
            return;
        }

        push(idx, segL, segR);
        int mid = (segL + segR) / 2;
        update(l, r, 2 * idx, segL, mid);
        update(l, r, 2 * idx + 1, mid + 1, segR);
        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }

    // 区间查询（递归函数）
    int query(int l, int r, int idx, int segL, int segR) {
        if (r < segL || l > segR) {
            return 0;
        }

        if (l <= segL && segR <= r) {
            return tree[idx];
        }

        push(idx, segL, segR);
        int mid = (segL + segR) / 2;
        int leftSum = query(l, r, 2 * idx, segL, mid);
        int rightSum = query(l, r, 2 * idx + 1, mid + 1, segR);
        return leftSum + rightSum;
    }

public:
    // 构造函数
    SegTree(const vector<int>& data) {
        n = data.size() - 1;
        size = 1;
        while (size < n) {
            size *= 2;
        }

        tree.resize(2 * size, 0);
        lazy.resize(2 * size, 0);

        build(data);
    }

    void flip(int l, int r) {
        update(l - 1, r - 1, 1, 0, size - 1);
    }

    int query(int l, int r) {
        return query(l - 1, r - 1, 1, 0, size - 1);
    }

    int getSize() const {
        return n;
    }
};

# 区间加、单点加；区间求和、单点求和

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
struct SegTree {
private:
    int n;                  // 原始数组长度
    int size;               // 线段树大小（2的幂次）
    vector<int> tree; // 线段树，存储区间和
    vector<int> lazy; // 懒标记，存储区间需要加的值

    // 构建线段树
    void build(const vector<int>& data) {
        // 修正：叶子节点索引计算
        for (int i = 1; i <= n; i++) {
            tree[size + i - 2] = data[i];  // 修正：索引从 size 开始
        }
        for (int i = size - 1; i >= 1; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    // 对节点应用懒标记
    void apply(int idx, int l, int r, int val) {
        tree[idx] += val * (r - l + 1);
        lazy[idx] += val;
    }

    // 下推懒标记
    void push(int idx, int l, int r) {
        if (lazy[idx] != 0) {
            int mid = (l + r) / 2;
            apply(2 * idx, l, mid, lazy[idx]);
            apply(2 * idx + 1, mid + 1, r, lazy[idx]);
            lazy[idx] = 0;
        }
    }

    // 区间加法更新（递归函数）
    void update(int l, int r, int val, int idx, int segL, int segR) {
        // 添加边界条件，避免死循环
        if (segL > segR) return;

        if (r < segL || l > segR) {
            return;
        }

        if (l <= segL && segR <= r) {
            apply(idx, segL, segR, val);
            return;
        }

        // 如果是叶子节点，直接返回
        if (segL == segR) return;

        push(idx, segL, segR);
        int mid = (segL + segR) / 2;
        update(l, r, val, 2 * idx, segL, mid);
        update(l, r, val, 2 * idx + 1, mid + 1, segR);
        tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
    }

    // 区间查询（递归函数）
    int query(int l, int r, int idx, int segL, int segR) {
        if (segL > segR) return 0;

        if (r < segL || l > segR) {
            return 0;
        }

        if (l <= segL && segR <= r) {
            return tree[idx];
        }

        if (segL == segR) return 0;

        push(idx, segL, segR);
        int mid = (segL + segR) / 2;
        int leftSum = query(l, r, 2 * idx, segL, mid);
        int rightSum = query(l, r, 2 * idx + 1, mid + 1, segR);
        return leftSum + rightSum;
    }

public:
    // 构造函数
    SegTree(const vector<int>& data) {
        n = data.size() - 1;
        size = 1;
        while (size < n) {
            size *= 2;
        }

        tree.resize(2 * size, 0);
        lazy.resize(2 * size, 0);

        build(data);
    }

    // 区间加法操作 [l, r] (闭区间，1-based)
    void update(int l, int r, int val) {
        if (l > r) return;
        update(l, r, val, 1, 1, n);
    }

    // 单点加法操作 (1-based)
    void update(int pos, int val) {
        update(pos, pos, val, 1, 1, n);
    }

    // 查询区间和 [l, r] (闭区间，1-based)
    int query(int l, int r) {
        if (l > r) return 0;
        return query(l, r, 1, 1, n);
    }

    // 查询单点值 (1-based)
    int query(int pos) {
        return query(pos, pos, 1, 1, n);
    }
};

# 区间加、区间赋值、区间求最值、区间求和

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
struct SegTree {
private:
    struct Node {
        int sum, mx;     // 区间和、区间最大值
        int add;         // 区间加懒标记
        int assign;      // 区间赋值懒标记
        bool has_assign;       // 是否存在赋值标记

        Node()
            : sum(0), mx(LLONG_MIN),
              add(0), assign(0), has_assign(false) {}
    };

    int n;
    vector<Node> t;

    // ================= build =======================
    void build(vector<int> &a, int p, int l, int r) {
        if (l == r) {
            t[p].sum = t[p].mx = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, p << 1, l, mid);
        build(a, p << 1 | 1, mid + 1, r);
        push_up(p);
    }

    // ================= push_up =====================
    void push_up(int p) {
        t[p].sum = t[p<<1].sum + t[p<<1|1].sum;
        t[p].mx = max(t[p<<1].mx, t[p<<1|1].mx);
    }

    // ================= apply 操作 ======================
    void apply_assign(int p, int l, int r, int v) {
        t[p].sum = v * (r - l + 1);
        t[p].mx = v;
        t[p].assign = v;
        t[p].add = 0;
        t[p].has_assign = true;
    }

    void apply_add(int p, int l, int r, int v) {
        t[p].sum += v * (r - l + 1);
        t[p].mx += v;

        if (t[p].has_assign) {
            t[p].assign += v;
        } else {
            t[p].add += v;
        }
    }

    // ================= push_down ====================
    void push_down(int p, int l, int r) {
        int mid = (l + r) >> 1;

        if (t[p].has_assign) {
            apply_assign(p<<1, l, mid, t[p].assign);
            apply_assign(p<<1|1, mid+1, r, t[p].assign);
            t[p].has_assign = false;
        }

        if (t[p].add != 0) {
            apply_add(p<<1, l, mid, t[p].add);
            apply_add(p<<1|1, mid+1, r, t[p].add);
            t[p].add = 0;
        }
    }


    // ================= update (assign) ===================
    void update_assign(int L, int R, int v, int p, int l, int r) {
        if (L <= l && r <= R) {
            apply_assign(p, l, r, v);
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        if (L <= mid) update_assign(L, R, v, p<<1, l, mid);
        if (R >  mid) update_assign(L, R, v, p<<1|1, mid+1, r);
        push_up(p);
    }

    // ================= update (add) ===================
    void update_add(int L, int R, int v, int p, int l, int r) {
        if (L <= l && r <= R) {
            apply_add(p, l, r, v);
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        if (L <= mid) update_add(L, R, v, p<<1, l, mid);
        if (R >  mid) update_add(L, R, v, p<<1|1, mid+1, r);
        push_up(p);
    }

    // ================= query sum ======================
    int query_sum(int L, int R, int p, int l, int r) {
        if (L <= l && r <= R)
            return t[p].sum;
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        int res = 0;
        if (L <= mid) res += query_sum(L, R, p<<1, l, mid);
        if (R >  mid) res += query_sum(L, R, p<<1|1, mid+1, r);
        return res;
    }

    // ================= query max ======================
    int query_max(int L, int R, int p, int l, int r) {
        if (L <= l && r <= R)
            return t[p].mx;
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        int res = LLONG_MIN;
        if (L <= mid) res = max(res, query_max(L, R, p<<1, l, mid));
        if (R >  mid) res = max(res, query_max(L, R, p<<1|1, mid+1, r));
        return res;
    }


public:

    SegTree(int n) : n(n) {
        t.resize(4 * n + 5);
    }

    // 对外可见接口（干净）
    void build(vector<int> &a) {
        build(a, 1, 1, n);
    }

    void update_assign(int L, int R, int v) {
        update_assign(L, R, v, 1, 1, n);
    }

    void update_add(int L, int R, int v) {
        update_add(L, R, v, 1, 1, n);
    }

    int query_sum(int L, int R) {
        return query_sum(L, R, 1, 1, n);
    }

    int query_max(int L, int R) {
        return query_max(L, R, 1, 1, n);
    }
};