线段树

Skyzhou666 · 2022-11-09 16:21:41 · 算法·理论

又臭又长

用于维护区间和，最大最小值等

线段树详解

这篇也不错

下面是板子题P3372 维护区间和

#include <iostream>
#define MAXN 100001
#define LL long long
using namespace std;

LL a[MAXN], tree[MAXN<<2], lazy[MAXN<<2];

void PushUp(LL k)
{
    tree[k] = tree[k<<1] + tree[k<<1|1];
}

void PushDown(LL l, LL r, LL k)
{
    if(lazy[k])
    {
        lazy[k<<1] += lazy[k];
        lazy[k<<1|1] += lazy[k];
        LL mid = (l + r) >> 1;
        tree[k<<1] += lazy[k] * (mid - l + 1);
        tree[k<<1|1] += lazy[k] * (r - (mid+1) + 1);
        lazy[k] = 0;
    }
}

void BuildTree(LL l, LL r, LL k)
{
    if(l == r) tree[k] = a[l];
    else
    {
        LL mid = (l + r) >> 1;
        BuildTree(l, mid , k<<1);
        BuildTree(mid + 1, r, k<<1|1);
        PushUp(k);
    }
}

void Update(LL L, LL R, LL l, LL r, LL k, LL p)
{
    if(l >= L && r <= R)
    {
        lazy[k] += p;
        tree[k] += p * (r - l + 1);
    }
    else
    {
        PushDown(l, r, k);
        LL mid = (l + r) >> 1;
        if(L <= mid) Update(L, R, l, mid, k<<1, p);
        if(R > mid) Update(L, R, mid+1, r, k<<1|1, p);
        PushUp(k);
    }
}

LL Query(LL L, LL R, LL l, LL r, LL k)
{
    if(l >= L && r <= R) return tree[k];
    else
    {
        PushDown(l, r, k);
        LL mid = (l + r) >> 1, re = 0;
        if(L <= mid) re += Query(L, R, l, mid, k<<1);
        if(R > mid) re += Query(L, R, mid+1, r, k<<1|1);
        return re;
    }
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for(LL x = 1; x <= n; x++) cin >> a[x];
    BuildTree(1, n, 1);
    //for(LL x = 1; x <= 4 * n; x++) cout << tree[x] << " ";
    //cout << endl;
    while(m--)
    {
        LL t, l, r, k;
        cin >> t;
        if(t == 1)
        {
            cin >> l >> r >> k;
            Update(l, r, 1, n, 1, k);
        }
        if(t == 2)
        {
            cin >> l >> r;
            cout << Query(l, r, 1, n, 1) << endl;
        }
    }
    return 0;
}

板子题2 P3373 维护区间和，但有加法和乘法运算（lazy好难搞啊啊）

#include <iostream>
#include <cstdio>
#define MAXN 100001
using namespace std;

long long a[MAXN], t[MAXN<<2], lp[MAXN<<2], lt[MAXN<<2], P;

void pushUp(long long k)
{
    t[k] = (t[k<<1] + t[k<<1|1]) % P;
}

void build(long long l, long long r, long long k)
{
    if(l == r) t[k] = a[l];
    else
    {
        long long mid = (l + r) >> 1;
        build(l, mid, k<<1);
        build(mid+1, r, k<<1|1);
        pushUp(k);
    }
}

void pushDown(long long l, long long r, long long k)
{
    //cout << l << " " << r << " " << k << endl; 
    //cout << lp[k] << " " << lt[k] << endl;
    lp[k<<1] = lp[k<<1] * lt[k] % P + lp[k];
    lp[k<<1|1] = lp[k<<1|1] * lt[k] % P + lp[k];

    lt[k<<1] = lt[k<<1] * lt[k] % P;
    lt[k<<1|1] = lt[k<<1|1] * lt[k] % P;

    long long mid = (l + r) >> 1;
    t[k<<1] = lt[k] * t[k<<1] % P + lp[k] * (mid - l + 1) % P;
    t[k<<1|1] = lt[k] * t[k<<1|1] % P + lp[k] * (r - (mid+1) + 1) % P;
    lp[k] = 0;
    lt[k] = 1;
}

void updatePlus(long long L, long long R, long long l, long long r, long long p, long long k)
{
    if(L <= l && r <= R)
    {
        lp[k] += p;
        t[k] += p * (r - l + 1) % P;
    }
    else
    {
        pushDown(l, r, k);
        long long mid = (l + r) >> 1;
        if(L <= mid) updatePlus(L, R, l, mid, p, k<<1);
        if(mid < R) updatePlus(L, R, mid+1, r, p, k<<1|1);
        pushUp(k);
    }
}

void updateTimes(long long L, long long R, long long l, long long r, long long p, long long k)
{
    if(L <= l && r <= R)
    {
        lt[k] = lt[k] * p % P;
        lp[k] = lp[k] * p % P;
        t[k] = t[k] * p % P;
    }
    else
    {
        pushDown(l, r, k);
        long long mid = (l + r) >> 1;
        if(L <= mid) updateTimes(L, R, l, mid, p, k<<1);
        if(R > mid) updateTimes(L, R, mid+1, r, p, k<<1|1);
        pushUp(k);
    }
}

long long query(long long L, long long R, long long l, long long r, long long k)
{
    if(L <= l && r <= R) return t[k] % P;
    else
    {
        pushDown(l, r, k);
        long long re = 0, mid = (l + r) >> 1;
        if(L <= mid) re += query(L, R, l, mid, k<<1) % P;
        if(mid < R) re += query(L, R, mid+1, r, k<<1|1) % P;
        return re % P;
    }
}

int main()
{
    //freopen("test.in", "r", stdin);
    long long n, m;
    cin >> n >> m >> P;
    for(long long x = 1; x <= n; x++) cin >> a[x];
    for(long long x = 1; x <= 4*n; x++) lt[x] = 1;
    build(1, n, 1);
    for(long long x = 1; x <= m; x++)
    {
        long long q, l, r, k;
        cin >> q;
        if(q == 2)
        {
            cin >> l >> r >> k;
            updatePlus(l, r, 1, n, k, 1);
        }
        else if(q == 1)
        {
            cin >> l >> r >> k;
            updateTimes(l, r, 1, n, k, 1);
        }
        else if(q == 3)
        {
            cin >> l >> r;
            cout << query(l, r, 1, n, 1) << endl;
        }
    }
    //fclose(stdin);
    return 0;
}

稍微改一下又成了在线维护RMQ

#include <iostream>
#define MAXN 100001
#define INF 0x7fffffff
#define int long long
using namespace std;

int a[MAXN], t[MAXN<<2], lazy[MAXN<<2];

void PushUp(int k)
{
    t[k] = max(t[k<<1], t[k<<1|1]);
}

void PushDown(int l, int r, int k)
{
    if(lazy[k])
    {
        lazy[k<<1] += lazy[k];
        lazy[k<<1|1] += lazy[k];
        t[k<<1] += lazy[k];
        t[k<<1|1] += lazy[k];
        lazy[k] = 0;
    }
}

void Build(int l, int r, int k)
{
    if(l == r) t[k] = a[l];
    else
    {
        int mid = (l+r)>>1;
        Build(l, mid, k<<1);
        Build(mid+1, r, k<<1|1);
        PushUp(k);
    }
}

void Update(int L, int R, int l, int r, int k, int p)
{
    if(l >= L && r <= R)
    {
        lazy[k] += p;
        t[k] += p;
    }
    else
    {
        PushDown(l, r, k);
        int mid = (l+r)>>1;
        if(L <= mid) Update(L, R, l, mid, k<<1, p);
        if(R > mid) Update(L, R, mid+1, r, k<<1|1, p);
        PushUp(k);
    }
}

int Query(int L, int R, int l, int r, int k)
{
    if(l >= L && r <= R) return t[k];
    else
    {
        PushDown(l, r, k);
        int mid = (l+r)>>1, re = -INF;
        if(L <= mid) re = max(re, Query(L, R, l, mid, k<<1));
        if(R > mid) re = max(re, Query(L, R, mid+1, r, k<<1|1));
        return re;
    }
}

signed main()
{
    int n, m;
    cin >> n >> m;
    for(int x = 1; x <= n; x++) cin >> a[x];
    Build(1, n, 1);
    while(m--)
    {
        int op, l, r, k;
        cin >> op;
        if(op == 1)
        {
            cin >> l >> r >> k;
            Update(l, r, 1, n, 1, k);
        }
        else
        {
            cin >> l >> r;
            cout << Query(l, r, 1, n, 1) << endl;
        }
    }
    return 0;
}

2025.3.30: 几年前写的史山RMQ居然是错的，一直不知道现在抄模板的时候才发现有bug，，，