概念
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在O(log N)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
操作
- 定义树
- pushdown
- pushup
- build
- modify
- query
定义树
struct node {
int l, r;
ll sum, add;
} tr[N * 4]; //经过推导，需要开四倍
pushdown
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) {
left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;
root.add = 0;
/*
更新过程中需要把父节点的懒标记更新到子节点
子节点继承父节点的懒标记，并更新自己的sum值
删除父节点的懒标记
*/
}
}pushup
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
//将父节点的sum更新，记得要直接=，而不是+=
}build
void build(int u, int l, int r)
{
if (l == r) {
tr[u] = { l, r, w[l], 0 };
} else {
tr[u] = { l, r };
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}midify
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
} else {
pushdown(u);//因为要把一个区间分开，所以要往下穿懒标记
int mid = (tr[u].l + tr[u].r) >> 1;
if (mid >= l)
modify(u << 1, l, r, d);
if (mid < r)
modify(u << 1 | 1, l, r, d);
pushup(u);//修改完以后要把子节点的值更新到父节点
}
}query
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
ll sum = 0;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid)
sum += query(u << 1, l, r);
if (mid < r)
sum += query(u << 1 | 1, l, r);
return sum;
}例题
例题链接
题解
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int w[N];
struct node {
int l, r;
ll sum, add;
} tr[N * 4];
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) {
left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
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, w[l], 0 };
} else {
tr[u] = { l, r };
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
} else {
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (mid >= l)
modify(u << 1, l, r, d);
if (mid < r)
modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
ll sum = 0;
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid)
sum += query(u << 1, l, r);
if (mid < r)
sum += query(u << 1 | 1, l, r);
return sum;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i];
build(1, 1, n);
while (m--) {
char op;
int l, r, d;
cin >> op;
if (op == 'Q') {
cin >> l >> r;
cout << query(1, l, r) << endl;
} else {
cin >> l >> r >> d;
modify(1, l, r, d);
}
}
}
int main()
{
// IOS;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}