线段树复健
OJ 上的题还没做完，下午再说（你
概念
一种二叉搜索树，通过二叉树形结构储存数据，能够解决大部分与区间操作有关的问题，当然应用范围不止于区间操作。
原理是用二分（？）维护一定的区间。
主体部分实现
建树
考虑递归建树，一直二分直到只剩一个数据为止。
展开代码
inline void pushup(ll k) {
sum[k] = sum[ls(k)] + sum[rs(k)];
} //修改和建树都要用到这个操作
inline void build(ll k, ll l, ll r) {
if(l == r) {sum[k] = a[l]; return; }
build(ls(k), l, mid(l, r));
build(rs(k), mid(l, r) + 1, r);
pushup(k);
}
懒标记（Lazy Tag）
通过标记当前节点左右儿子需要修改的量，减少重复计算，降低时间复杂度。
展开代码
inline void add(ll k, ll l, ll r, ll v) {
lazy[k] += v, sum[k] += v * len(l, r);
}
inline void pushdown(ll k, ll l, ll r) {
add(ls(k), l, mid(l, r), lazy[k]);
add(rs(k), mid(l, r) + 1, r, lazy[k]);
lazy[k] = 0;
} //下传标记，修改左右儿子的值
区间操作
核心是不断二分并下传标记，当二分到需求的区间内时返回。
区间修改和查询的示例：
展开代码
inline void update(ll k, ll l, ll r, ll x, ll y, ll v) {
if(l >= x && r <= y) {add(k, l, r, v); return; }
pushdown(k, l, r);
if(x <= mid(l, r)) update(ls(k), l, mid(l, r), x, y, v);
if(mid(l, r) < y) update(rs(k), mid(l, r) + 1, r, x , y, v);
pushup(k); //更新区间的值
}
inline ll query(ll k, ll l, ll r, ll x, ll y) {
if(l >= x && r <= y) return sum[k];
ll ans = 0;
if(x <= mid(l, r)) ans += query(ls(k), l, mid(l, r), x, y);
if(mid(l, r) < y) ans += query(rs(k), mid(l, r) + 1, r, x, y);
return ans;
}
例题
延绵的山峰
没找到原题
展开题面
有一座延绵不断、跌宕起伏的山，最低处海拔为 \(0\), 最高处海拔不超过 \(8848\) 米，从这座山的一端走到另一端的过程中，每走 \(1\) 米海拔就升高或降低 \(1\) 米。有 \(Q\) 个登山队计划在这座山的不同区段登山，当他们攀到各自区段的最高峰时，就会插上队旗。请你写一个程序找出他们插旗的高度。
区间最值，需要注意的是输入数据是编号 \(0\sim n\) 的高度。
展开代码
#include <bits/stdc++.h>
#define ll long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mid(l, r) ((l + r) >> 1)
#define len(l, r) (r - l + 1)
#define MyWife Cristallo
using namespace std;
const int N = 5 * 1e6 + 5;
ll n, m, a[N], x, y, z, b, sum[N], lazy[N];
inline void pushup(ll k) {
sum[k] = max(sum[ls(k)], sum[rs(k)]);
}
inline void build(ll k, ll l, ll r) {
if(l == r) {sum[k] = a[l]; return; }
build(ls(k), l, mid(l, r));
build(rs(k), mid(l, r) + 1, r);
pushup(k);
}
/*
inline void add(ll k, ll l, ll r, ll v) {
lazy[k] += v, sum[k] += v * len(l, r);
}
inline void pushdown(ll k, ll l, ll r) {
add(ls(k), l, mid(l, r), lazy[k]);
add(rs(k), mid(l, r) + 1, r, lazy[k]);
lazy[k] = 0;
}
inline void update(ll k, ll l, ll r, ll x, ll y, ll v) {
if(l >= x && r <= y) {add(k, l, r, v); return; }
pushdown(k, l, r);
if(x <= mid(l, r)) update(ls(k), l, mid(l, r), x, y, v);
if(mid(l, r) < y) update(rs(k), mid(l, r) + 1, r, x , y, v);
pushup(k);
}
*/
inline ll query(ll k, ll l, ll r, ll x, ll y) {
//cout << k << " " << sum[k] << endl;
if(l >= x && r <= y) return sum[k];
ll ans = -1;
//pushdown(k, l, r);
if(x <= mid(l, r)) ans = max(ans, query(ls(k), l, mid(l, r), x, y));
if(mid(l, r) < y) ans = max(ans, query(rs(k), mid(l, r) + 1, r, x, y));
return ans;
}
int main() {
scanf("%lld", &n);
scanf("%lld", &a[0]);
for(ll i = 1; i <= n; ++i) scanf("%lld", a + i);
build(1, 1, n);
scanf("%lld", &m);
while(m--) {
scanf("%lld%lld", &x, &y);
//cout << x << " " << y << endl;
printf("%lld\n", query(1, 1, n, x, y));
}
return 0;
}
感谢伟大的 2k3h 先生做出的贡献：
