线段树笔记(html/模板)
例题1:最大数(JSOI 2008)
线段树(单点修改、区间查询)
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
[HTML_REMOVED]
思路:
- 线段树维护:左右端点(l,r)、最大值(v)。
- 区间最大值 = max(左半区间最大值, 右半区间最大值)
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 200010;
#define ls u << 1 // 表示根节点的左儿子
#define rs u << 1 | 1 // 表示根节点的右儿子
/* 标记#表示第一次没熟悉的地方 */
int m, p, n;
struct Node{
int l, r;
int v; // 区间[l,r]的最大值,由于只用存最大值就存一个v
}tr[N * 4];
void pushup(int u){
tr[u].v = max(tr[ls].v, tr[rs].v);
}
void build(int u, int l, int r){
tr[u] = {l, r}; // #给结点赋值l,r
if(l == r) return ;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点完全包含在查询区间内
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if(l <= mid) v = query(ls, l, r);
if(r > mid) v = max(v, query(rs, l, r)); // 区间断点是mid 和 mid + 1
// # 以上均为l,r区间,只管当前节点区间内最大值,有交集查就完事
return v;
}
void modify(int u, int x, int v) // u 节点编号,x 修改位置, v 修改值
{
if(x == tr[u].l && x == tr[u].r)
tr[u].v = v;
else{ // # 此处else必不可少,否则到了叶节点还要瞎几把更新
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(ls, x, v); // 根据 x 的位置来分类
if (x > mid) modify(rs, x, v);
pushup(u);
}
}
int main(){
scanf("%d%d", &m, &p);
build(1, 1, m);
int last = 0;
while(m--){
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'Q'){
last = query(1, n - x + 1, n); // 查询操作
printf("%d\n", last);
}
if(*op == 'A'){
modify(1, n + 1, (last + x) % p); // 插入操作
n++;
}
}
return 0;
}
例题2:你能回答这些问题吗?(《算法竞赛进阶指南》)
线段树(区间查询、单点修改)
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
[HTML_REMOVED]
思路:
题意:给定数列A,两种操作,查询[x, y]内最大连续子段和 和 将A[x]修改成 y。
思考:最大子段和有哪几种情况组成情况 ->不断增加维护信息来确定是否能实现题目中的操作
AC代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 500010;
int n, m;
int w[N];
struct Node{
int l, r;
int lmax, rmax, tmax, sum;
}tr[N << 2];
void pushup(Node & u, Node & l, Node & r){
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
u.tmax = max(max(l.tmax, r.tmax), r.lmax + l.rmax); // # 最大子段和可能在
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
if(l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
else{
tr[u] = {l, r};
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v){
if(x == tr[u].l && x == tr[u].r) tr[u] = {x, x, v, v, v, v}; // # 修改tr[u]值
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(ls, x, v);
else modify(rs, x, v);
pushup(u);
}
}
Node query(int u, int l, int r){
if(l == tr[u].l && r == tr[u].r) return tr[u];
else{
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(ls, l, r);
else if(l > mid) return query(rs, l, r);
else{
auto left = query(ls, l, r); // 最大子段和在左右两个区间可能分别取得
auto right = query(rs, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &w[i]);
build(1, 1, n);
while(m--){
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if(k == 1){
if(x > y) swap(x, y);
Node res = query(1, x, y);
printf("%d\n", res.tmax);
}
if(k == 2){
modify(1, x, y);
}
}
return 0;
}
例题3:区间最大公约数(《算法竞赛进阶指南》)
线段树(区间查询、区间修改)、差分
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
思路:
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
typedef long long ll;
const int N = 500010;
int n, m;
ll w[N];
struct Node{
int l, r;
ll sum, d;
} tr[N * 4];
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
void pushup(Node & u, Node & l, Node & r){
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
if(l == r){
ll b = w[r] - w[r - 1]; // l和r才是w索引,u不是
tr[u] = {l, r, b, b};
}
else{
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, ll v){
if(x == tr[u].l && x == tr[u].r){
ll b = tr[u].sum + v;
tr[u] = {x, x, b, b};
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(ls, x, v);
else modify(rs, x, v);
pushup(u);
}
}
Node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u]; // 查询区间包括了树所有区间,直接返回这小部分区间结果
else{
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(ls, l, r); // 查询区间在树节点左半边,一定return!!!
else if(l > mid) return query(rs, l, r); // 查询区间在树节点右半边,一定return!!!
else{ // 查询区间在树节点两边都有
auto left = query(ls, l, r);
auto right = query(rs, l, r);
Node res;
pushup(res, left, right); // 利用pushup特性,创造一个新的节点res作为区间查询值
return res;
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%lld", &w[i]);
build(1, 1, n);
ll d;
int l, r;
char op[2];
while(m--){
scanf("%s%d%d", op, &l, &r);
if(*op == 'Q'){
auto left = query(1, 1, l);
Node right = {0, 0, 0, 0};
if(l + 1 <= r)
right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(left.sum, right.d)));
}
else{
scanf("%lld", &d);
modify(1, l, d);
if(r + 1 <= n) modify(1, r + 1, -d); // 修改不能越界
}
}
return 0;
}
例题4:一个简单的整数问题2(《算法竞赛进阶指南》)
线段树(lazy标记、区间修改、区间查询)
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
思路:
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
typedef long long ll;
const int N = 100010;
int n,m;
int w[N];
struct Node{
int l, r;
ll sum, add;
}tr[N];
void pushup(int u){
tr[u].sum = tr[ls].sum + tr[rs].sum;
}
void build(int u, int l, int r){
if(l == r) tr[u] = {l, l, w[l], 0}
else{
tr[u] = {l, r}
int mid = l + r >> 1;
build(1, l, mid), build(1, mid + 1, r);
pushup(u);
}
}
void pushdown(int u){
auto &root = tr[u], &left = tr[ls], &right = tr[rs];
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 modify(int u, int l, int r, int d){
if(l <= tr[u].l && r >= tr[u].r){
tr[u].sum += (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(r <= mid) modify(ls, l, r, d);
if(l > mid) modify(rs, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r){
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll sum = 0;
if(l <= mid) sum += query(ls, l, r);
if(r > mid) sum += query(rs, l, r);
return sum;
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &w[i]);
}
build(1, 1, n);
char op[2];
int l, r, d;
while(m--){
scanf("%s%d%d", op, &l, &r);
if(*op == 'C'){
scanf("%d", &d);
modify(1, l, r, d);
}
else{
printf("%lld\n", query(1, l, r));
}
}
return 0;
return 0;
}
例题5:亚特兰蒂斯(《算法竞赛进阶指南》)
扫描线、线段树(特殊pushdown优化)
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
[HTML_REMOVED]
思路:
AC代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 100010;
int n;
vector<double> ys; // vector存取离散化后数组
struct Node{
int l, r, cnt;
double len; // 区间长度
}tr[N * 2]; // 维护一个区间
struct Segment{
double x, y1, y2;
int k;
bool operator < (Segment & s){
return x < s.x;
}
}seg[N << 3]; // 存储线段
int find(double y){
return lower_bound(ys.begin(), ys.end(), y) - ys.begin(); // 查询y索引
}
void pushup(int u){
if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; // 区间被覆盖,长度是区间长度(涉及区间长度需要ys)
else if(tr[u].l != tr[u].r){
tr[u].len = tr[ls].len + tr[rs].len; // 非叶子结点len由子区间决定
}
else
tr[u].len = 0; // 叶子结点且cnt = 0
}
void build(int u, int l, int r){
tr[u] = {l, r, 0, 0}; // 建树其余值为0 可以直接赋值
if(l != r){
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
// 因为值都为0无需pushup
}
}
void modify(int u, int l, int r, int k){
if(tr[u].l >= l && tr[u].r <= r){ // 当前区间包含在修改区间之中
tr[u].cnt += k;
pushup(u); // 修改就pushup
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(ls, l, r, k); // 在节点区间左边有交集,修改左边
if(r > mid) modify(rs, l, r, k); // 在节点区间右边有交集,修改右边
pushup(u);
}
}
int main(){
int T = 1;
while(1){
ys.clear(); // 多组数据清空vecotr
scanf("%d", &n);
if(!n) break;
for(int i = 0, j = 0; i < n; i++){
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
seg[j++] = {x1, y1, y2, 1}; // 依次存入线段到seg中
seg[j++] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2); // 依次存入y1 y2
}
// 离散化
sort(ys.begin(), ys.end()); // 先排序
ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 后去重
build(1, 0, ys.size() - 2);
sort(seg, seg + 2 * n); // 排序线段
double res = 0;
for(int i = 0; i < 2 * n; i++){
if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x); // 扫描线有效长度 * 宽度 = 面积
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k); // 由于线段数维护一个区间,查询点的位置后应该-1
}
printf("Test case #%d\n", T++);
printf("Total explored area: %.2lf\n\n", res);
}
return 0;
}
例题6:维护序列(《信息学奥赛一本通》 , AHOI2009)
线段树
[HTML_REMOVED]
[HTML_REMOVED]题面[HTML_REMOVED]
[HTML_REMOVED]
[HTML_REMOVED]
思路:
AC代码:
这,不支持html展开图片,着实有点蛋疼