洛谷P3373題目概述

洛谷P3373是一道關于線段樹的模板題，題目名稱為“【模板】線段樹 2”。題目的主要要求是對一個長度為 n 的數列進行如下操作：

1. 將某區間每個數乘上一個數。
2. 將某區間每個數加上一個數。
3. 求出某區間所有數的和。

線段樹簡介

線段樹是一種二叉樹數據結構，常用于高效處理區間查詢和更新操作。它可以將一個區間劃分為多個子區間，每個節點代表一個區間，通過維護這些節點的信息，可以在 $O(\log n)$ 的時間復雜度內完成區間查詢和更新操作。

代碼詳細講解

1. 頭文件和宏定義

#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 400002
#define lson (root*2)
#define rson (root*2+1)

• #include <iostream> 和 #include <cmath> 分別引入輸入輸出流和數學庫。
• using namespace std; 表示使用標準命名空間。
• MAXN 定義了線段樹數組的最大長度，通常為 $4n$，因為線段樹的節點數最多為 $4n$。
• lson 和 rson 分別表示當前節點的左子節點和右子節點的編號。

2. 全局變量

int MOD;
long long sgmt[MAXN], lazy_mul[MAXN], lazy_add[MAXN];

• MOD 是取模的基數，用于防止結果溢出。
• sgmt[MAXN] 是線段樹數組，用于存儲每個節點所代表區間的和。
• lazy_mul[MAXN] 和 lazy_add[MAXN] 是懶標記數組，分別用于標記乘法和加法操作。

3. push_up 函數

void push_up(int root) {sgmt[root] = sgmt[lson] + sgmt[rson];sgmt[root] %= MOD;
}

• 該函數用于將左右子節點的信息更新到父節點。具體來說，將左子節點和右子節點所代表區間的和相加，并取模后賦值給父節點。

4. push_down 函數

void push_down(int root, int len) {if (lazy_mul[root] == 1 && lazy_add[root] == 0) return;lazy_mul[lson] *= lazy_mul[root], lazy_mul[lson] %= MOD;lazy_mul[rson] *= lazy_mul[root], lazy_mul[rson] %= MOD;lazy_add[lson] *= lazy_mul[root], lazy_add[lson] %= MOD;lazy_add[rson] *= lazy_mul[root], lazy_add[rson] %= MOD;lazy_add[lson] += lazy_add[root], lazy_add[lson] %= MOD;lazy_add[rson] += lazy_add[root], lazy_add[rson] %= MOD;sgmt[lson] *= lazy_mul[root], sgmt[lson] %= MOD;sgmt[lson] += (len/2)*lazy_add[root], sgmt[lson] %= MOD;sgmt[rson] *= lazy_mul[root], sgmt[rson] %= MOD;sgmt[rson] += (len/2)*lazy_add[root], sgmt[rson] %= MOD;lazy_mul[root] = 1, lazy_add[root] = 0;
}

• 該函數用于將當前節點的懶標記下推到左右子節點。
• 首先判斷當前節點是否有懶標記，如果 lazy_mul[root] 為 1 且 lazy_add[root] 為 0，則說明沒有懶標記，直接返回。
• 然后將當前節點的乘法懶標記和加法懶標記下推到左右子節點，并更新左右子節點的線段樹數組和懶標記數組。
• 最后將當前節點的懶標記重置為初始值。

5. update 函數

void update(int a, int b, long long c, long long d, int l, int r, int root) {if (a <= l && r <= b) {sgmt[root] *= c, sgmt[root] %= MOD;sgmt[root] += (r-l+1)*d, sgmt[root] %= MOD;lazy_mul[root] *= c, lazy_mul[root] %= MOD;lazy_add[root] *= c, lazy_add[root] %= MOD;lazy_add[root] += d, lazy_add[root] %= MOD;return;}push_down(root,r-l+1);int mid = (l+r)/2;if (a <= mid) update(a,b,c,d,l,mid,lson);if (b > mid) update(a,b,c,d,mid+1,r,rson);push_up(root);
}

• 該函數用于更新區間 [a, b] 內的所有數，將每個數先乘上 c，再加上 d。
• 如果當前節點所代表的區間完全包含在 [a, b] 內，則直接更新當前節點的線段樹數組和懶標記數組。
• 否則，先將當前節點的懶標記下推，然后遞歸更新左右子節點，最后更新當前節點的線段樹數組。

6. query 函數

long long query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];push_down(root,r-l+1);long long ans = 0;int mid = (l+r)/2;if (a <= mid) ans += query(a,b,l,mid,lson), ans %= MOD;if (b > mid) ans += query(a,b,mid+1,r,rson), ans %= MOD;return ans;
}

• 該函數用于查詢區間 [a, b] 內所有數的和。
• 如果當前節點所代表的區間完全包含在 [a, b] 內，則直接返回當前節點的線段樹數組的值。
• 否則，先將當前節點的懶標記下推，然后遞歸查詢左右子節點，并將結果相加。

7. build 函數

void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l,mid,lson);build(mid+1,r,rson);push_up(root);return;
}

• 該函數用于構建線段樹。
• 如果當前節點所代表的區間只有一個元素，則直接返回。
• 否則，遞歸構建左右子節點，然后更新當前節點的線段樹數組。

8. main 函數

int main() {for (int i = 1; i < MAXN; i++)lazy_mul[i] = 1;int n, m; cin >> n >> m >> MOD;int npot = 1 << (int)ceil(log2(n));for (int i = 0; i < n; i++)cin >> sgmt[npot+i];n = npot;int l = 1, r = n, root = 1;build(l,r,root);while (m--) {int op, a, b, c; cin >> op >> a >> b;if (op == 1) {cin >> c; update(a,b,c,0,l,r,root);} else if (op == 2) {cin >> c; update(a,b,1,c,l,r,root);} elsecout << query(a,b,l,r,root)%MOD << endl;}return 0;
}

• 首先將所有乘法懶標記初始化為 1。
• 然后讀取數列的長度 n、操作的次數 m 和取模的基數 MOD。
• 接著將數列存儲在線段樹數組中，并將 n 擴展為 2 的冪次方。
• 調用 build 函數構建線段樹。
• 最后循環處理 m 次操作，根據操作類型調用 update 或 query 函數。

復雜度分析

• 時間復雜度：每次更新和查詢操作的時間復雜度均為 $O(\log n)$，因此總的時間復雜度為 $O(m\log n)$。
• 空間復雜度：線段樹數組和懶標記數組的空間復雜度均為 $O(4n)$，因此總的空間復雜度為 $O(n)$。

完整代碼：

// P3373 【模板】線段樹 2
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 400002
#define lson (root*2)
#define rson (root*2+1)int MOD;
long long sgmt[MAXN], lazy_mul[MAXN], lazy_add[MAXN];void push_up(int root) {sgmt[root] = sgmt[lson] + sgmt[rson];sgmt[root] %= MOD;
}void push_down(int root, int len) {if (lazy_mul[root] == 1 && lazy_add == 0) return;lazy_mul[lson] *= lazy_mul[root], lazy_mul[lson] %= MOD;lazy_mul[rson] *= lazy_mul[root], lazy_mul[rson] %= MOD;lazy_add[lson] *= lazy_mul[root], lazy_add[lson] %= MOD;lazy_add[rson] *= lazy_mul[root], lazy_add[rson] %= MOD;lazy_add[lson] += lazy_add[root], lazy_add[lson] %= MOD;lazy_add[rson] += lazy_add[root], lazy_add[rson] %= MOD;sgmt[lson] *= lazy_mul[root], sgmt[lson] %= MOD;sgmt[lson] += (len/2)*lazy_add[root], sgmt[lson] %= MOD;sgmt[rson] *= lazy_mul[root], sgmt[rson] %= MOD;sgmt[rson] += (len/2)*lazy_add[root], sgmt[rson] %= MOD;lazy_mul[root] = 1, lazy_add[root] = 0;
}void update(int a, int b, long long c, long long d, int l, int r, int root) {if (a <= l && r <= b) {sgmt[root] *= c, sgmt[root] %= MOD;sgmt[root] += (r-l+1)*d, sgmt[root] %= MOD;lazy_mul[root] *= c, lazy_mul[root] %= MOD;lazy_add[root] *= c, lazy_add[root] %= MOD;lazy_add[root] += d, lazy_add[root] %= MOD;return;}push_down(root,r-l+1);int mid = (l+r)/2;if (a <= mid) update(a,b,c,d,l,mid,lson);if (b > mid) update(a,b,c,d,mid+1,r,rson);push_up(root);
}long long query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];push_down(root,r-l+1);long long ans = 0;int mid = (l+r)/2;if (a <= mid) ans += query(a,b,l,mid,lson), ans %= MOD;if (b > mid) ans += query(a,b,mid+1,r,rson), ans %= MOD;return ans;
}void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l,mid,lson);build(mid+1,r,rson);push_up(root);return;
}int main() {for (int i = 1; i < MAXN; i++)lazy_mul[i] = 1;int n, m; cin >> n >> m >> MOD;int npot = 1 << (int)ceil(log2(n));for (int i = 0; i < n; i++)cin >> sgmt[npot+i];n = npot;int l = 1, r = n, root = 1;build(l,r,root);while (m--) {int op, a, b, c; cin >> op >> a >> b;if (op == 1) {cin >> c; update(a,b,c,0,l,r,root);} else if (op == 2) {cin >> c; update(a,b,1,c,l,r,root);} elsecout << query(a,b,l,r,root)%MOD << endl;}return 0;
}

感謝閱讀