Segment Tree线段树

线段树的作用范围：区间单点更新和覆盖，区间多点更新和覆盖。
时间复杂度：O（logN）
原理图：


线段树

对于一个长度为N的数组，我们将一个区间（LR的区间）划分成两个单元区间。每个区域分为左区域和右区域，左区域的范围为L（L+R）/2，右区域的范围为（L+R）/2+1~R。当左区域等于右区域的时候，就说明走到最底层了。对于每个区域的下标我们规定，左区域的下标=2父节点的下标，右区域的下标=2父节点的下标+1。

结构体
struct node
{
    int tl, tr;
    int lazy, val;
} tree[4*maxn];

建树
void Push(int id)
{
    tree[id].val=tree[id*2].val+tree[id*2+1].val;
}

void Build(int id, int tl, int tr)
{
    tree[id].tl=tl;
    tree[id].tr=tr;
    tree[id].val=0;
    tree[id].lazy=0;
    if(tl== tr) tree[id].val=a[tl];
    else
    {
        int tm=(tl+tr)/2;
        Build(id*2, tl, tm);
        Build(id*2+1, tm+1, tr);
        Push(id);
    }
}

更新
void Pushdown(int id)
{
    if(tree[id].lazy==0) return ;
    tree[id*2].lazy=tree[id*2+1].lazy=tree[id].lazy;
    tree[id*2].val=(tree[id*2].tr-tree[id*2].tl+1)*tree[id].lazy;
    tree[id*2+1].val=(tree[id*2+1].tr-tree[id*2+1].tl+1)*tree[id].lazy;
    tree[id].lazy=0;
}

void Update(int id, int ql, int qr, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql>tr || qr<tl) return ;
    if(ql<=tl && tr<=qr)
    {
        tree[id].lazy=val;
        tree[id].val=(tree[id].tr-tree[id].tl+1)*tree[id].lazy;
        return ;
    }
    Pushdown(id);
    Update(id*2, ql, qr, val);
    Update(id*2+1, ql, qr, val);
    Push(id);
}

查询
int Query(int id, int ql, int qr)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    int ans=0;
    if(ql>tr || qr<tl) return 0;
    if(ql<=tl && tr<=qr) return tree[id].val;
    Pushdown(id);
    ans+=Query(id*2, ql, qr);
    ans+=Query(id*2+1, ql, qr);
    Push(id);
    return ans;
}

线段树的单点更新

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
const int inf = 0x7fffffff;
int a[maxn];

struct node
{
    int tl, tr, val;
} tree[4*maxn];

void Push(int id)
{
    tree[id].val=min(tree[id*2].val, tree[id*2+1].val);
}

void Build(int id, int tl, int tr)
{
    tree[id].tl=tl;
    tree[id].tr=tr;
    if(tl==tr) tree[id].val=a[tl];
    else
    {
        int mid=(tl+tr)/2;
        Build(id*2, tl, mid);
        Build(id*2+1, mid+1, tr);
        Push(id);
    }
}

void Update(int id, int i, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(i==tl && i==tr) tree[id].val=val;
    else
    {
        int tm=(tl+tr)/2;
        if(tm>=i) Update(id*2, i, val);
        else Update(id*2+1, i, val);
        Push(id);
    }
}

int Query(int id, int ql, int qr)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql<=tl && tr<=qr) return tree[id].val;
    int tm=(tl+tr)/2;
    int res1=inf, res2=inf;
    if(tm>=ql) res1=Query(id*2, ql, qr);
    if(tm<qr) res2=Query(id*2+1, ql, qr);
    return min(res1, res2);
}

int main()
{
    int i, n, q, op, l, r, val;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &q);
    Build(1, 1, n);
    while(q--)
    {
        scanf("%d", &op);
        if(op==0)
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", Query(1, l, r));
        }
        else
        {
            scanf("%d%d", &i, &val);
            Update(1, i, val);
        }
    }
    return 0;
}

线段树的区间更新

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
const int inf = 0x7fffffff;

int a[maxn];
struct node
{
    int tl, tr, val, lazy;
} tree[4*maxn];

void push(int id)
{
    tree[id].val=tree[id*2].val+tree[id*2+1].val;
}

void pushdown(int id)
{
    if(tree[id].lazy==0) return ;
    tree[id*2].lazy=tree[id*2+1].lazy=tree[id].lazy;
    tree[id*2].val=(tree[id*2].tr-tree[id*2].tl+1)*tree[id].lazy;
    tree[id*2+1].val=(tree[id*2+1].tr-tree[id*2+1].tl+1)*tree[id].lazy;
    tree[id].lazy=0;
}

void build(int id, int tl, int tr)
{
    tree[id].tl=tl;
    tree[id].tr=tr;
    tree[id].val=0;
    tree[id].lazy=0;
    if(tl==tr) tree[id].val=a[tl];
    else
    {
        int tm=(tl+tr)/2;
        build(id*2, tl, tm);
        build(id*2+1, tm+1, tr);
        push(id);
    }
}

void update(int id, int ql, int qr, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql>tr || qr<tl) return ;
    if(ql<=tl && tr<=qr)
    {
        tree[id].lazy=val;
        tree[id].val=(tree[id].tr-tree[id].tl+1)*tree[id].lazy;
        return ;
    }
    pushdown(id);
    update(id*2, ql, qr, val);
    update(id*2+1, ql, qr, val);
    push(id);
}

int query(int id, int ql, int qr)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    int ans=0;
    if(ql>tr || qr<tl) return 0;
    if(ql<=tl && tr<=qr) return tree[id].val;
    pushdown(id);
    ans+=query(id*2, ql, qr);
    ans+=query(id*2+1, ql, qr);
    push(id);
    return ans;
}

int main()
{
    int n, i, q, l, r, val, op;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    scanf("%d", &q);
    while(q--)
    {
        scanf("%d", &op);
        if(op==0)
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
        else
        {
            scanf("%d%d%d", &l, &r, &val);
            update(1, l, r, val);
        }
    }
    return 0;
}

离散化

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
const int inf = 0x7fffffff;

int vis[maxn];
int ans=0;
int a[maxn];
struct re
{
    int l, r;
} q[maxn];

struct node
{
    int tl, tr, val, lazy;
} tree[4*maxn];

void Build(int id, int tl, int tr)
{
    tree[id].tl=tl;
    tree[id].tr=tr;
    tree[id].val=0;
    tree[id].lazy=0;
    if(tl+1==tr) return ;
    else
    {
        int tm=(tl+tr)/2;
        Build(id*2, tl, tm);
        Build(id*2+1, tm, tr);
    }
}

void Pushdown(int id)
{
    if(tree[id].lazy==0) return ;
    tree[id*2].lazy=tree[id*2+1].lazy=tree[id].lazy;
    tree[id*2].val=tree[id*2+1].val=tree[id].lazy;
    tree[id].lazy=0;
}

void Update(int id, int ql, int qr, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql<=tl && tr<=qr)
    {
        tree[id].lazy=val;
        tree[id].val=val;
        return ;
    }
    Pushdown(id);
    int tm=(tl+tr)/2;
    if(tm>ql) Update(id*2, ql, qr, val);
    if(tm<qr) Update(id*2+1, ql, qr, val);
}

void Query(int id, int ql, int qr)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(tl+1==tr)
    {
        if(vis[tree[id].val]==0)
        {
            vis[tree[id].val]=1;
            ans++;
        }
        return ;
    }
    Pushdown(id);
    int tm=(tl+tr)/2;
    if(tm>ql) Query(id*2, ql, qr);
    if(tm<qr) Query(id*2+1, ql, qr);
}

void init()
{
    memset(vis,0,sizeof(vis));
    memset(a,0,sizeof(a));
    ans=0;
}

int main()
{
    init();
    int i, n, l, k=0;
    scanf("%d%d", &n, &l);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        a[k++]=q[i].l;
        a[k++]=q[i].r;
    }
    sort(a, a+k);
    int len=unique(a, a+k)-a;
    Build(1, 1, len);
    for(i=1; i<=n; i++)
    {
        int l=lower_bound(a,a+len,q[i].l)-a+1;
        int r=lower_bound(a,a+len,q[i].r)-a+1;
        Update(1, l, r, i);
    }
    vis[0]=1;
    Query(1, 1, len);
    printf("%d\n", ans);
    return 0;
}

双标记线段树

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
const int inf = 0x7fffffff;

struct node
{
    int tl, tr;
    int lazyset, lazyadd, val;
} tree[4*maxn];
int a[maxn];

void push(int id)
{
    tree[id].val=tree[2*id].val+tree[2*id+1].val;
}

void build(int id, int tl, int tr)
{
    tree[id].tl=tl;
    tree[id].tr=tr;
    if(tl==tr) tree[id].val=a[tl];
    else
    {
        int tm=(tr+tl)/2;
        build(id*2,tl,tm);
        build(id*2+1,tm+1,tr);
        push(id);
    }
}

void pushdown(int id)
{
    if(tree[id].lazyset!=0)
    {
        tree[id*2].lazyset=tree[id].lazyset;
        tree[id*2+1].lazyset=tree[id].lazyset;
        tree[id*2].lazyadd=tree[id].lazyadd;
        tree[id*2+1].lazyadd=tree[id].lazyadd;
        int ans=tree[id].lazyset+tree[id].lazyadd;
        tree[id*2].val=(tree[id*2].tr-tree[id*2].tl+1)*ans;
        tree[id*2+1].val=(tree[id*2+1].tr-tree[id*2+1].tl+1)*ans;
        tree[id].lazyset=0;
        tree[id].lazyadd=0;
    }
    else if(tree[id].lazyadd!=0)
    {
        tree[id*2].lazyadd+=tree[id].lazyadd;
        tree[id*2+1].lazyadd+=tree[id].lazyadd;
        tree[id*2].val+=(tree[id*2].tr-tree[id*2].tl+1)*tree[id].lazyadd;
        tree[id*2+1].val+=(tree[id*2+1].tr-tree[id*2+1].tl+1)*tree[id].lazyadd;
        tree[id].lazyadd=0;
    }
}

void putset(int id, int val)
{
    tree[id].lazyadd=0;
    tree[id].lazyset=val;
    tree[id].val=(tree[id].tr-tree[id].tl+1)*val;
}

void Set(int id, int ql, int qr, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql>tr || qr<tl) return ;
    if(ql<=tl && tr<=qr)
    {
        putset(id, val);
        return ;
    }
    pushdown(id);
    Set(id*2, ql, qr, val);
    Set(id*2+1, ql, qr, val);
    push(id);
}

void putadd(int id, int val)
{
    tree[id].lazyadd+=val;
    tree[id].val+=(tree[id].tr-tree[id].tl+1)*val;
}

void add(int id, int ql, int qr, int val)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    if(ql>tr || qr<tl) return ;
    if(ql<=tl && tr<=qr)
    {
        putadd(id, val);
        return ;
    }
    pushdown(id);
    add(id*2, ql, qr, val);
    add(id*2+1, ql, qr, val);
    push(id);
}

int getval(int id, int ql, int qr)
{
    int tl=tree[id].tl;
    int tr=tree[id].tr;
    int ans=0;
    if(ql>tr || qr<tl) return 0;
    if(ql<=tl && tr<=qr) return tree[id].val;

    pushdown(id);
    ans+=getval(id*2, ql, qr);
    ans+=getval(id*2+1, ql, qr);
    push(id);
    return ans;
}

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1; i<=n+1; i++)
        scanf("%d",&a[i]);
    build(1,1,n+1);
    while(q--)
    {
        int op,l,r,val;
        scanf("%d%d%d%d",&op,&l,&r,&val);
        if(!op)add(1,l+1,r+1,val);
        else Set(1,l+1,r+1,val);
        printf("%d\n",getval(1,1,n+1));
    }
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 从树状数组到线段树
    在已知了树状数组的使用方法，那么便可以用它来解决一些实际问题了，比如说下面一道经典题：敌兵布阵 ：HDU：1166...
    碧影江白阅读 4,697评论 0赞 2
  • 静态主席树
    主席树的作用是寻找一个序列的某个区间的第k大(小)如:给出一个序列a1,a2...an，有若干个询问，每个询问形如...
    Gitfan阅读 3,523评论 0赞 0
  • 面试高级算法梳理笔记
    归去来兮。 1.1 说明 本篇为《挑战程序设计竞赛（第2版）》[http://www.ituring.com.cn...
    尤汐Yogy阅读 14,900评论 0赞 160
  • 可持久化线段树
    在这里，所谓“可持久化”的数据结构并非指将数据存在非易失的存储器上，而是指保存了数据修改的历史信息。比如说对可持久...
    njzwj阅读 9,597评论 0赞 0
  • 288-叶子-定向打卡
    1、SCQA 场景 冲突 问题 答案 2、SQA 3、SQAA
    Milly叶子阅读 890评论 0赞 0