算法竞赛进阶指南-第五章-线段树

Monday. March 06, 2023 - 11 mins

一种基于分支思想的二叉树结构.与树状数组相比,线段树是一种更加通用的结构

保存线段树的数组长度要不小于4N才能保证不会越界

线段树的基本用途是对序列进行维护,支持查询与修改指令

线段树作为一种比较通用的数据结构,能够维护各式各样的信息,前提是这些信息容易按照区间进行划分和合并(又称满足区间可加性)

建立一颗线段树并在每个结点上保存对应区间的最大值的代码

struct SegmentTree{
    int l, r;
    int dat;
} t[SIZE * 4];//struct 数组存储线段树
void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;//结点p代表区间[l,r]
    if(l == r) { t[p].dat = a[l]; return;}//叶节点
    int mid = (l +r) /2;//折半
    build(p * 2, l, mid);//左子节点[l,mid],编号p*2
    build(p * 2 + 1, mid + 1, r);//右子节点[mid+1,r],编号p*2+1
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);//从下往上传递信息(此处传递的是最大值信息,具体可根据问题修改)
}
build(1,1,n);//调用入口

线段树的单点修改 O(logN)

从根节点出发,递归找到代表区间[x,x]的叶节点,然后从下往上更新[x,x]以及它的所有祖先节点上保存的信息

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);//x属于左半区间
    else change(p * 2 + 1, x, v);//x属于右半区间
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);//从下往上更新信息
}
change(1,x,v);//调用入口

线段树的区间查询 O(logN)

int ask(int p, int l, int r)
{
    if(l <= t[p].l && r >= t[p].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;
}
cout << ask(1,l,r) << '\n';//调用入口

Can you answer on these queries III

典型的线段树问题,把上面几个函数套入,维护区间和sum,区间最大连续子段和dat,紧靠左端的最大连续子段和lmax,紧靠右端的最大连续子段和rmax

完善build,change和ask函数中传递和取得的信息

#include <bits/stdc++.h>
using namespace std;
struct SegmentTree
{
    int l, r;
    long long dat;
    long long sum;
    long long lmax;
    long long rmax;
};
SegmentTree t[2000005]; // struct 数组存储线段树
int n, m;
int a[500005];
void buildd(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].dat = a[l];
        t[p].sum = a[l];
        t[p].lmax = a[l];
        t[p].rmax = a[l];
        return;
    }
    int mid = (l + r) / 2;
    buildd(p * 2, l, mid);
    buildd(p * 2 + 1, mid + 1, r);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
    t[p].lmax = max(t[p * 2].lmax, t[p * 2].sum + t[p * 2 + 1].lmax);
    t[p].rmax = max(t[p * 2 + 1].rmax, t[p * 2 + 1].sum + t[p * 2].rmax);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
    t[p].dat = max(t[p].dat, t[p * 2].rmax + t[p * 2 + 1].lmax);
}
void changee(int p, int x, int v)
{
    if (t[p].l == t[p].r)
    {
        t[p].dat = v;
        t[p].sum = v;
        t[p].lmax = v;
        t[p].rmax = v;
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if (x <= mid)
        changee(p * 2, x, v);
    else
        changee(p * 2 + 1, x, v);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
    t[p].lmax = max(t[p * 2].lmax, t[p * 2].sum + t[p * 2 + 1].lmax);
    t[p].rmax = max(t[p * 2 + 1].rmax, t[p * 2 + 1].sum + t[p * 2].rmax);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
    t[p].dat = max(t[p].dat, t[p * 2].rmax + t[p * 2 + 1].lmax);
}
SegmentTree ask(int p, int l, int r)
{
    if (l <= t[p].l && r >= t[p].r)
        return t[p];
    int mid = (t[p].l + t[p].r) / 2;
    SegmentTree val;
    if (l <= mid && r > mid)
    {
        SegmentTree t1, t2;
        t1 = ask(p * 2, l, r), t2 = ask(p * 2 + 1, l, r);
        val.lmax = max(t1.lmax, t1.sum + t2.lmax);
        val.rmax = max(t2.rmax, t2.sum + t1.rmax);
        val.dat = max(t1.dat, t2.dat);
        val.dat = max(val.dat, t1.rmax + t2.lmax);
    }
    else if (l <= mid)
        val = ask(p * 2, l, r);
    else if (r > mid)
        val = ask(p * 2 + 1, l, r);
    return val;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    buildd(1, 1, n);
    while (m--)
    {
        int tt, x, y;
        cin >> tt >> x >> y;

        if (tt == 1)
        {
            if (x > y)
                swap(x, y);
            cout << ask(1, x, y).dat << '\n';
        }
        else
            changee(1, x, y);
    }
}

Interval GCD

写了一两个小时,没写出来,不知道哪的问题,写法应该是对的,过了2/7的数据

gcd(x,y,z) = gcd(x,y-x,z-y);

构造一个差分序列,用线段树维护其区间最大公约数

构建树状数组维护A数组

延迟标记

除了在修改指令中直接划分成的O(logN)歌结点之外,对任意结点的修改都延迟到”在后续操作中递归进入它的父节点”时再进行.这样一来,每条查询或修改指令的时间复杂度都降低到了O(logN)