Segment Tree线段树

作者: 1QzUPm_09F | 来源:发表于2017-07-25 10:53 被阅读62次

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

线段树

对于一个长度为N的数组，我们将一个区间（L_{R的区间）划分成两个单元区间。每个区域分为左区域和右区域，左区域的范围为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;
}

Segment Tree线段树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构