一篇講解很好的線段樹博客：數據結構--線段樹篇_數據結構線段樹-CSDN博客
一、區間查詢 無修改：
（一）最值問題：
1.P1816 忠誠 - 洛谷
思路：
????????模板。
注意：
????????無。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */int v[N];
struct Node
{int l, r;int minn;
} tr[N * 4];void pushup(int u)
{tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, v[l]};return;}tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}int query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].minn;}int mid = tr[u].l + tr[u].r >> 1;int minn = MAX;if (l <= mid)minn = min(minn, query(u << 1, l, r));if (r > mid)minn = min(minn, query(u << 1 | 1, l, r));return minn;
}void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)cin >> v[i];build(1, 1, n);while (m--){int l, r;cin >> l >> r;cout << query(1, l, r) << ' ';}cout << endl;
}int main()
{ioscc;solve();return 0;
}2.P1886 滑動窗口 /【模板】單調隊列 - 洛谷
思路：
????????模板。
注意：
????????無。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e6 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */int v[N];
struct Node
{int l, r;int minn, maxx;
} tr[N * 4];void pushup(int u)
{tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, v[l], v[l]};return;}tr[u] = {l, r, 0, 0};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}int queryMin(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].minn;}int mid = tr[u].l + tr[u].r >> 1;int minn = MAX;if (l <= mid)minn = min(minn, queryMin(u << 1, l, r));if (r > mid)minn = min(minn, queryMin(u << 1 | 1, l, r));return minn;
}int queryMax(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].maxx;}int mid = tr[u].l + tr[u].r >> 1;int maxx = MIN;if (l <= mid)maxx = max(maxx, queryMax(u << 1, l, r));if (r > mid)maxx = max(maxx, queryMax(u << 1 | 1, l, r));return maxx;
}void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; ++i)cin >> v[i];build(1, 1, n);for (int i = 1; i <= n - k + 1; ++i)cout << queryMin(1, i, i + k - 1) << ' ';cout << endl;for (int i = 1; i <= n - k + 1; ++i)cout << queryMax(1, i, i + k - 1) << ' ';cout << endl;
}int main()
{ioscc;solve();return 0;
}二、區間查詢 單點修改：
（一）區間和問題：
1.P2068 統計和 - 洛谷
思路：
????????模板。
注意：
????????無。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */struct Node
{int l, r;ll sum;
} tr[N * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, 0};return;}tr[u] = {l, r, 0};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}ll query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;int mid = tr[u].l + tr[u].r >> 1;ll sum = 0;if (l <= mid)sum += query(u << 1, l, r);if (r > mid)sum += query(u << 1 | 1, l, r);return sum;
}void update(int u, int x, int v)
{if (tr[u].l == x && tr[u].r == x)tr[u].sum += v;else{int mid = tr[u].l + tr[u].r >> 1;if (x <= mid)update(u << 1, x, v);elseupdate(u << 1 | 1, x, v);pushup(u);}
}void solve()
{int n, m;cin >> n >> m;build(1, 1, n);while (m--){char op;int a, b;cin >> op >> a >> b;if (op == 'x')update(1, a, b);elsecout << query(1, a, b) << endl;}
}int main()
{ioscc;solve();return 0;
}2.P2184 貪婪大陸 - 洛谷
思路：
? ? ? ? 區間修改時使用一種類差分的思想，每次埋地雷的時候只在區間左右端點累加一次值，這樣就將問題裝換為了單點修改；查詢時我們再使用前綴和思想統計區間 [l, r] 區間內的地雷數。具體實現就是使用線段樹維護兩個sum，既區間左端點的地雷和區間右端點的地雷；在查詢區間 [l ,r] 時，就可以用 [1, r] 的起點數減去 [1, l] 的終點數。
注意：
? ? ? ? 無。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
#define ls u << 1
#define rs u << 1 | 1
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */struct Node
{int l, r;int sum[2];
} tr[N * 4];void pushup(int u, int k)
{tr[u].sum[k] = tr[u << 1].sum[k] + tr[u << 1 | 1].sum[k];
}void build(int u, int l, int r)
{tr[u] = {l, r, 0, 0};if (l == r)return;int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}ll query(int u, int l, int r, int k)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum[k];int mid = tr[u].l + tr[u].r >> 1;ll sum = 0;if (l <= mid)sum += query(u << 1, l, r, k);if (r > mid)sum += query(u << 1 | 1, l, r, k);return sum;
}void update(int u, int x, int k)
{if (tr[u].l == tr[u].r){++tr[u].sum[k];return;}int mid = tr[u].l + tr[u].r >> 1;if (x <= mid)update(u << 1, x, k);elseupdate(u << 1 | 1, x, k);pushup(u, k);
}void solve()
{int n, m;cin >> n >> m;build(1, 1, n);while (m--){int op, l, r;cin >> op >> l >> r;if (op == 1)update(1, l, 0), update(1, r, 1);elsecout << query(1, 1, r, 0) - query(1, 1, l - 1, 1) << endl;}
}int main()
{ioscc;solve();return 0;
}（二）最值問題
1.P1198 [JSOI2008] 最大數 - 洛谷
思路：
? ? ? ? 模板。
注意：
? ? ? ? 雖然線段樹初始為空的，也要初始化 m 個位置為后續做準備。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = -2e18;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */struct Node
{int l, r;ll maxx;
} tr[N << 2];void pushup(int u)
{tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}void build(int u, int l, int r)
{tr[u] = {l, r, 0};if (l == r)return;int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}ll query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u].maxx;int mid = tr[u].l + tr[u].r >> 1;ll maxx = MIN;if (l <= mid)maxx = max(maxx, query(u << 1, l, r));if (r > mid)maxx = max(maxx, query(u << 1 | 1, l, r));return maxx;
}void update(int u, int x, int v)
{if (tr[u].l == tr[u].r){tr[u].maxx = v;return;}int mid = tr[u].l + tr[u].r >> 1;if (x <= mid)update(u << 1, x, v);elseupdate(u << 1 | 1, x, v);pushup(u);
}void solve()
{ll n = 0, m;int mod;cin >> m >> mod;build(1, 1, m);int last = 0;while (m--){char op;int x;cin >> op >> x;if (op == 'Q'){last = query(1, n - x + 1, n);cout << last << endl;}else{++n;int ans = ((ll)x + last) % mod;update(1, n, ans);}}
}int main()
{ioscc;solve();return 0;
}三、區間查詢 區間修改：
（一）區間和問題：
1.P2357 守墓人 - 洛谷
思路：
????????模板。
注意：
????????開ll。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */ll v[N];
struct Node
{int l, r;ll sum;ll add;
} tr[N * 4];void pushup(int u)
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{if (tr[u].add){tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);tr[u << 1].add += tr[u].add;tr[u << 1 | 1].add += tr[u].add;tr[u].add = 0;}
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, v[l], 0};return;}tr[u] = {l, r, 0, 0};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}ll query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;ll sum = 0;if (l <= mid)sum += query(u << 1, l, r);if (r > mid)sum += query(u << 1 | 1, l, r);return sum;
}void update(int u, int l, int r, int v)
{if (tr[u].l >= l && tr[u].r <= r){tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * v;tr[u].add += v;return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)update(u << 1, l, r, v);if (r > mid)update(u << 1 | 1, l, r, v);pushup(u);
}void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)cin >> v[i];build(1, 1, n);while (m--){int op;int l, r, v;cin >> op;if (op == 1){cin >> l >> r >> v;update(1, l, r, v);}else if (op == 2){cin >> v;update(1, 1, 1, v);}else if (op == 3){cin >> v;update(1, 1, 1, -v);}else if (op == 4){cin >> l >> r;cout << query(1, l, r) << endl;}elsecout << query(1, 1, 1) << endl;}
}int main()
{ioscc;solve();return 0;
}（二）區間最值+區間和問題：
1.P3130 [USACO15DEC] Counting Haybale P - 洛谷
思路：
? ? ? ? 線段樹維護區間、最小值、區間和、懶標記。
注意：
????????更新懶標記時也需將節點的最小值加上懶標記的值。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */ull v[N];
struct Node
{int l, r;ull minn;ull sum;ull add;
} tr[N * 4];void pushup(int u)
{tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u)
{if (tr[u].add){tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);tr[u << 1].minn += tr[u].add;tr[u << 1 | 1].minn += tr[u].add;tr[u << 1].add += tr[u].add;tr[u << 1 | 1].add += tr[u].add;tr[u].add = 0;}
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, v[l], v[l], 0};return;}tr[u] = {l, r, 0, 0, 0};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}ull querySum(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].sum;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;ull sum = 0;if (l <= mid)sum += querySum(u << 1, l, r);if (r > mid)sum += querySum(u << 1 | 1, l, r);return sum;
}ull queryMin(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].minn;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;ull minn = MAX;if (l <= mid)minn = min(minn, queryMin(u << 1, l, r));if (r > mid)minn = min(minn, queryMin(u << 1 | 1, l, r));return minn;
}void update(int u, int l, int r, int v)
{if (tr[u].l >= l && tr[u].r <= r){tr[u].sum += (ull)(tr[u].r - tr[u].l + 1) * v;tr[u].minn += v;tr[u].add += v;return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)update(u << 1, l, r, v);if (r > mid)update(u << 1 | 1, l, r, v);pushup(u);
}void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)cin >> v[i];build(1, 1, n);while (m--){char op;int a, b, c;cin >> op;if (op == 'M'){cin >> a >> b;cout << queryMin(1, a, b) << endl;}else if (op == 'P'){cin >> a >> b >> c;update(1, a, b, c);}else{cin >> a >> b;cout << querySum(1, a, b) << endl;}}
}int main()
{ioscc;solve();return 0;
}（三）區間和+區間乘
1.P3373 【模板】線段樹 2 - 洛谷
思路：
? ? ? ? 維護乘和加兩個懶標記，由于乘法優先級高于加法，所以當前節點的值為 sum * mul + add,
當父節點下傳懶標記時，設 m,a 為父節點下傳的乘法與加法懶標記，所以當前節點值為 (sum *
mul + add) * m + a，可得?sum * mul * m + add * m + a ，所以mul和sum的更新值為 mul = mul
* m，add = add * m + a。
注意：
? ? ? ? 開ll，乘和加的優先級。
代碼：
#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* ----------------- 有乘就強轉，前綴和開ll ----------------- */int mod;
ll v[N];
struct Node
{int l, r;ll sum;ll add, mul;
} tr[N << 2];void pushup(int u)
{tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}void calc(Node &t, ll m, ll a)
{t.sum = (t.sum * m % mod + (t.r - t.l + 1) * a % mod) % mod;t.mul = t.mul * m % mod;t.add = (t.add * m + a) % mod;
}void pushdown(int u)
{calc(tr[u << 1], tr[u].mul, tr[u].add);calc(tr[u << 1 | 1], tr[u].mul, tr[u].add);tr[u].add = 0;tr[u].mul = 1;
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, v[l], 0, 1};return;}tr[u] = {l, r, 0, 0, 1};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);
}ll query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r){return tr[u].sum % mod;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;ll sum = 0;if (l <= mid)sum += query(u << 1, l, r) % mod;if (r > mid)sum += query(u << 1 | 1, l, r) % mod;return sum % mod;
}void update(int u, int l, int r, int m, int a)
{if (tr[u].l >= l && tr[u].r <= r){calc(tr[u], m, a);return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)update(u << 1, l, r, m, a);if (r > mid)update(u << 1 | 1, l, r, m, a);pushup(u);
}void solve()
{int n, m;cin >> n >> m >> mod;for (int i = 1; i <= n; ++i)cin >> v[i];build(1, 1, n);while (m--){int op;int x, y, v;cin >> op >> x >> y;if (op == 1){cin >> v;update(1, x, y, v, 0);}else if (op == 2){cin >> v;update(1, x, y, 1, v);}elsecout << query(1, x, y) % mod << endl;}
}int main()
{ioscc;solve();return 0;
}
![題海拾貝：P8598 [藍橋杯 2013 省 AB] 錯誤票據](http://pic.xiahunao.cn/題海拾貝：P8598 [藍橋杯 2013 省 AB] 錯誤票據)
