Segment Tree线段树

线段树的作用范围：区间单点更新和覆盖，区间多点更新和覆盖。
时间复杂度：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;
}

最后编辑于：2017.12.09 02:20:57

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,445评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,889评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,047评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,760评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,745评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,638评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,011评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,669评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,923评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,655评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,740评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,406评论 4赞 320
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,995评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,961评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,023评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,483评论 2赞 342

Segment Tree线段树

推荐阅读更多精彩内容