线段树

__Green_tick__ · 2025-01-18 20:34:15 · 算法·理论

线段树

前置知识

树
分治
适用背景

线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在 O(\log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

算法过程

线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

有个大小为 5 的数组 a=\{10,11,12,13,14,15,16,17,18,19\}，要将其转化为线段树。

如何构建

如图：

构建如上线段树，将其放入数组：

void build(long long id,long long l,long long r){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){//递归边界
        tree[id].sum=arr[l];
        return;
    }else{
        long long mid=(l+r)>>1;
        build(id<<1,l,mid);//向下递归
        build(id<<1|1,mid+1,r);
        PushUp(id);
    }
    return;
}

区间查询

现需要查询 a_4+a_5+\dots+a_9 的值：

即 tree_{17}+tree_{11}+tree_{6}+tree_{14}。

long long query(long long id,long long l,long long r){
    if(l<=tree[id].l && tree[id].r<=r){
        return tree[id].sum;
    }else{
        long long mid=(tree[id].l+tree[id].r)>>1;//取中间
        long long sum=0;//当前总和
        if(l<=mid) sum+=query(id<<1,l,r);//即 id/2
        if(mid<r) sum+=query(id<<1|1,l,r);//即 id/2+1
        return sum;
    }
}

单点修改

现需要将 a_8+1：

void change(long long id,long long p,long long k){
    if(tree[id].l==tree[id].r){
        tree[id].sum+=k;
        return;
    }else{
        long long mid=(tree[id].l+tree[id].r)>>1;
        if(p<=mid) change(id<<1,p,k);
        else change(id<<1|1,p,k);
        PushUp(id);//即 tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
        return;
    }
}

综合以上：

#include<bits/stdc++.h>
using namespace std;
const long long MaxN=1e5+10;
long long n,m;
long long arr[MaxN];
struct Tree{
    long long l,r,sum;
}tree[MaxN<<2];

void PushUp(long long id){
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    return;
}

void build(long long id,long long l,long long r){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        tree[id].sum=arr[l];
        return;
    }else{
        long long mid=(l+r)>>1;

        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);

        PushUp(id);
    }
    return;
}

void change(long long id,long long p,long long k){
    if(tree[id].l==tree[id].r){
        tree[id].sum+=k;
        return;
    }else{
        long long mid=(tree[id].l+tree[id].r)>>1;

        if(p<=mid) change(id<<1,p,k);
        else change(id<<1|1,p,k);

        PushUp(id);
        return;
    }
}

long long query(long long id,long long l,long long r){
    if(l<=tree[id].l && tree[id].r<=r){
        return tree[id].sum;
    }else{
        long long mid=(tree[id].l+tree[id].r)>>1;
        long long sum=0;

        if(l<=mid) sum+=query(id<<1,l,r);
        if(mid<r) sum+=query(id<<1|1,l,r);
        return sum;
    }
}

int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
    }

    build(1,1,n);

    for(long long i=0;i<m;i++){
        long long opt,x,y;
        cin>>opt>>x>>y;

        if(opt==1){
            change(1,x,y);
        }else{
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
}

如上代码可通过 P3374 【模板】树状数组 1。

显然，线段树可以实现树状数组所可以实现的题目。

Lazy Tag优化

懒惰标记就是在对一颗树的所有节点进行某种统一操作时，只对根节点做一个标记表示它的子树都要进行这个操作，但是懒惰标记仅可用于能够计算出若对树上的每个节点进行操作时，能够通过根节点直接算出查询值。这可能有些复杂。

举个栗子

灰色为 Lazy Tag 标记。

执行下一步：

将 tree_1 和 tree_3 的 Lazy Tag 解除，更改 tree_1 和 tree_3 的值，并下放 Lazy Tag。