线段树专题总结

线段树

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点.

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为$O(logN)$,而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩.

–摘自百度百科
线段树的机理还是比较好理解的.
查询某个区间,需要将其划分成许多小区间,若区间左右端点与线段树节点左右端点一致,就可以返回结果.

1
2
3
4
5
6
7
8
9
int query(int l,int r,int p)
{
    if(tree[p].l==l&&tree[p].r==r)
        return tree[p].sum;
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)return query(l,r,ls);
    else if(l>mid)return query(l,r,rs);
    else return query(l,mid,ls)+query(mid+1,r,rs);
}

最经典的区间求和代码.
三条if-else语句的意思大概是:

如果区间的右端点比左儿子的右端点小,则区间被完全包含在左儿子中,查询左儿子.
如果区间的左端点比右儿子的左端点大,则区间被完全包含在右儿子中,查询右儿子.
否则,区间被左右儿子平分秋色,将左右儿子查询结果融合.
最终结果是区间左右端点与节点左右端点一致时,返回这个儿子的值.

这就是最经典的区间求和的的代码啦.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void update(int x,int a,int p)
{
    if(tree[p].l==tree[p].r)
    {
        tree[p].sum=a;
        return ;
    }
    int mid=tree[p].l+tree[p].r>>1;
    if(x<=mid)update(x,a,ls);
    else update(x,a,rs);
    Up(p);
}

单点更新的代码如上,也是判断这个单点在线段树节点中的位置,并进行向上更新,即Push_up:tree[p].sum=tree[ls].sum+tree[rs].sum
完整的单点更新,区间求和代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#define ls (p<<1)
#define rs (p<<1|1)
const int maxn=1e5+5;
struct T
{
    int l,r,sum;
}tree[maxn<<2];
int a[maxn],n,m;
void Up(int p)
{
    tree[p].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int p)
{
    tree[p].l=l;tree[p].r=r;
    if(l==r)
    {
        tree[p].sum=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    Up(p);
}
int query(int l,int r,int p)
{
    if(tree[p].l==l&&tree[p].r==r)
        return tree[p].sum;
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)return query(l,r,ls);
    else if(l>mid)return query(l,r,rs);
    else return query(l,mid,ls)+query(mid+1,r,rs);
}
void update(int x,int a,int p)
{
    if(tree[p].l==tree[p].r)
    {
        tree[p].sum=a;
        return ;
    }
    int mid=tree[p].l+tree[p].r>>1;
    if(x<=mid)update(x,a,ls);
    else update(x,a,rs);
    Up(p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    char tmp[10];
    build(1,n,1);
    while(m--)
    {
        int x,y;
        scanf("%s%d%d",tmp,&x,&y);
        if(tmp[0]=='Q')
            printf("%d\n",query(x,y,1));
        else update(x,y,1);
    }
}

区间更新怎么办呢,难道要将区间的一个个单点扫过来吗?不,我们可以像区间求和一样去更新一个个小区间.但是我们到if(tree[p].l==l&&tree[p].r==r)的时候就会return了.此时我们引入一个新思想—-懒标记
当我们在$[L,R]$这个区间return的时候,我们给$[L,R]$这个节点传上一个懒标记,以后访问到这个节点的时候,再进行向下更新,更新儿子节点的值.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void Down(int p)
{
    if(tree[p].lazy==0)return;
    ll &t=tree[p].lazy;
 
    tree[ls].lazy+=t;
    tree[ls].sum+=t*(tree[ls].R-tree[ls].L+1);
 
    tree[rs].lazy+=t;
    tree[rs].sum+=t*(tree[rs].R-tree[rs].L+1); 
    t=0; 
}
void update(int L,int R,int a,int p)
{
    if(tree[p].L==L&&tree[p].R==R)
    {
        tree[p].lazy+=a;
        tree[p].sum+=a*(R-L+1);
        return;
    }
    Down(p);
    int mid=(tree[p].L+tree[p].R)>>1;
    if(R<=mid)update(L,R,a,ls);
    else if(L>mid)update(L,R,a,rs);
    else update(L,mid,a,ls),update(mid+1,R,a,rs);
    Up(p);
}
ll query(int L,int R,int p)
{
    if(tree[p].L==L&&tree[p].R==R)
        return tree[p].sum;
    Down(p);
    int mid=(tree[p].L+tree[p].R)>>1;
    if(R<=mid) return query(L,R,ls);
    else if(L>mid)return query(L,R,rs);
    else return query(L,mid,ls)+query(mid+1,R,rs);
} 

在一切访问到节点的时候向下更新就可以啦.
线段树不但可以解决区间求和问题,还可以解决区间最值问题(将sum的更新改为max和min值的更新就可以了),区间连续和问题(存从左开始的连续和,从右开始的连续和,以及最大连续和,和分治思想类似,需要从儿子up答案),区间存在问题(在线段树上二分,存在的区间)等等…
涉及到前缀的都可以先想树状数组,涉及到区间的再想线段树就可以了.
为什么呢?