信息学竞赛模板（十二）— 线段树

2021-08-07 · 71次阅读 · 原创 · 数据结构与算法

线段树

给定数组 a，多次查询给定区间 [L, R] 内数组 a 的最大值。

const int SIZE = 1e5+5;
int a[SIZE];

struct SegmentTree{
    int l, r;
    int dat;
} t[SIZE * 4];

//建树
void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){
        t[p].dat = a[l];
        return;
    }
    
    int mid = (l + r) / 2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

//将位置在 x 的元素值改为 v，同时更新状态
void change(int p, int x, int v){
    if(t[p].l == t[p].r){
        t[p].dat = v;
        return;
    }
    
    int mid = (t[p].l + t[p].r) / 2;
    if(x <= mid) change(p*2, x, v);
    else change(p*2+1, x, v);
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

// 查询区间 l-r 内的目标值
int ask(int p, int l, int r){
    if(l <= t[p].l && t[p].r <= r) return t[p].dat;
    
    int mid = (t[p].l + t[p].r) / 2;
    int val = -(1<<30);
    if(l <= mid) val = max(val, ask(p*2, l, r));
    if(r > mid) val = max(val, ask(p*2+1, l, r));
    return val;
}

//建树，修改，查询
build(1, 1, n);
change(1, x, v);
ask(1, 2, 8);

例题

蓝桥杯-第八大奇迹

标题：	信息学竞赛模板（十二）— 线段树
链接：	https://www.fightingok.cn/detail/127
更新：	2022-09-18 22:41:14
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

信息学竞赛模板（十二）— 线段树

线段树

例题

Cyan