线段树

应用：搜索区间最值，总和，更新区间，更新点。时间复杂度：O(log n)

线段树

一直用一分为二的方法将区间数组层层变小，可以看成是一颗二叉树，故名线段树。

树状数组求和及点修改代码还有模拟过程：

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 100007

int sum[maxn*2*2];///sum求和
int a[maxn],n;///存原数组，下标为n-1

///l，r表示当前节点区间，rt表示当前节点编号
void build(int l,int r,int rt)///建树
{///
    if(l==r)///到达叶节点
    {
        sum[rt]=a[l];///存储数组值
        return ;
    }
    int m=(l+r)/2;///左右递归

    build(l,m,rt*2);
    build(m+1,r,rt*2+1);

    ///更新信息，子节点更新了，所以本节点也需要更新信息
    sum[rt]=sum[rt*2]+sum[rt*2+1];///只有拆分的点才走一步，叶节点直接标记sum数组了
}

///点修改，假设a[p]=a[p]+3
///l，r表示当前节点区间，rt表示当前节点编号
void update(int p,int c,int l,int r,int rt)
{
    if(l==r)///到达叶节点，修改后返回
    {
        sum[rt]=sum[rt]+c;
        return ;
    }
    int m=(l+r)/2;
    ///根据条件判断往左调用还是往右
    if(p<=m) update(p,c,l,   m, rt*2);
    else     update(p,c,m+1, r, rt*2+1);
    sum[rt] = sum[rt*2] + sum[rt*2+1];
}


///区间查询，   L,R表示操作区间
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)///在区间内，直接返回
        return sum[rt];

    int m=(l+r)/2;

    ///累计答案
    int ans=0;
    if(L<=m) ans=ans+query(L,R,l,m,rt*2);
    if(R>m)  ans=ans+query(L,R,m+1,r,rt*2+1);

    return ans;
}

int main()
{
    cin>>n;///n=13
    for(int i=1;i<=n;i++)
        cin>>a[i];

    build(1,n,1);

    int p,c;
    cin>>p>>c;///p=3; c=7

    update(p,c,1,n,1);
    int L,R;
    cin>>L>>R;///L=5; R=8
    cout<<query(L,R,1,n,1)<<endl;
    return 0;
}
/*
模拟线段树
a数组
下标  1  2  3  4  5  6  7  8  9  10  11  12  13
元素  1  2  3  4  1  2  3  4  1  2   3   4   1
建树
build(1,13,1);                       build(1,1,16)---sum[16]=1
m=14/2=7             build(1,2,8)< build(2,2,17)---sum[17]=2
                build(1,4,4)< build(3,4,9)< build(3,3,18)---sum[18]=3
                                       build(4,4,19)---sum[19]=4
build(1,7,2);< m=4
                                build(5,6,10)<build(5,5,20)---sum[20]=1
                build(5,7,5)<                   build(6,6,21)---sum[21]=2
                                build(7,7,11)----sum[11]=3


                                                     build(8,8,24)---sum[24]=4
                                    build(8,9,12) <  build(9,9,25)---sum[25]=1
                    build(8,10,6)<  build(10,10,13)---sum[13]=2

build(8,13,3);< m=10                                  build(11,11,28)---sum[28]=3
                                    build(11,12,14) <
                    build(11,13,7)<                      build(12,12,29)---sum[29]=4
                                    build(13,13,15)---sum[15]=1




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

元素 31  16  15  10  6   7   8   3   7   3    3    5    2    7    1    1    2    3    4    1    2              4    1              3   4

p=3,c=7

a数组
下标  1  2  3  4  5  6  7  8  9  10  11  12  13
元素  1  2  8  4  1  2  3  4  1  2   3   4   1
a[3]=a[3]+7=10


update(3,7,1,13,1);
{
    m=7;
    p<=m;yes
    update(3,7,1,7,2)
    {
        m=4;
        p<=m;yes
        update(3,7,1,4,4)
        {
            m=2;
            p<=m;no
            update(3,7,3,4,9)
            {
                m=3;
                p<=m;yes
                update(3,7,3,3,18)
                {
                    l=r; -----sum[18]=sum[18]+c=3+7=10
                    return ;
                }
                sum[9]=sum[18]+sum[19]=10+4=14
            }
            sum[4]=sum[8]+sum[9]=3+14=17
        }
        sum[2]=sum[4]+sum[5]=17+6=23
    }
    sum[1]=sum[2]+sum[3]=23+15=38
}

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

元素 38  23  15  17  6   7   8   3  14   8    3    5    2    7    1    1    2   10    4    1    2              4    1              3   4

查找 5 到 8 的和有多少
L=5，R=8
query(5,8,1,13,1)
{    no
    m=7;
    int ans=0;
    5<=7 yes ans = ans + query(5,8,1,7,2)=0+6
                        {    no
                            m=4;
                            int ans=0;
                            5<=4 no
                            8>4  yes;  ans=ans+query(5,8,5,7,5)=0+6=6
                                                {5<=5&&7<=8 yes return sum[5]=6

                                                }
                            return 6;
                        }
    8>7  yes ans = ans + query(5,8,8,13,3)=6+4=10;
                        {    no
                            m=10;
                            int ans=0;
                            5<=10 yes;  ans=ans+query(5,8,8,10,6)=0+4=4
                                                {no
                                                    m=9;
                                                    int ans=0;
                                                    5<=9 yes ans=ans+query(5,8,8,9,12)=0+4=4
                                                                     {no
                                                                         m=8
                                                                         int ans=0;
                                                                         5<=8 yes ans=ans+query(5,8,8,8,24)=0+4=4
                                                                                         {
                                                                                             l=r;
                                                                                             return sum[24]=4
                                                                                         }
                                                                         8>8 no;
                                                                         return ans=4;
                                                                     }
                                                    8>9 no;
                                                    return ans=4;
                                                }
                            8>10 no;
                            return ans=4
                        }
    return ans=10;
}
*/

线段树搜索区间最值裸题：（NYOJ119，本题优先使用RMQ算法，时间允许也可以用线段树）

士兵杀敌（三）

时间限制：2000 ms | 内存限制：65535 KB

难度：5

描述

南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。

所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。

现在，请你写一个程序，帮小工回答南将军每次的询问吧。

注意，南将军可能询问很多次。

输入

只有一组测试数据
第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)
随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的杀敌数。
再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。

输出

对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。

样例输入

样例输出

1
7

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const int maxx=1e6+5;
int n,t,L,R;
int big,small;///全局变量存储各区间的最值

struct node
{
    int maxa,minn;
};///结构体保存最大最小值
int a[maxx];
node sum[4*maxx];

void build(int l,int r,int rt)///建立线段树
{
    if(l==r)///遇到叶子节点，递归出口
    {
        sum[rt].maxa=a[l];
        sum[rt].minn=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    sum[rt].maxa=max( sum[rt*2].maxa,sum[rt*2+1].maxa );///同时更新父亲结点的最值
    sum[rt].minn=min( sum[rt*2].minn,sum[rt*2+1].minn );
}

void query1(int l,int r,int rt)///更变查询区间
{
    if(L<=l && r<=R)
    {

        big=max(big,sum[rt].maxa);///更新最值
        small=min(small,sum[rt].minn);
        return ;
    }
    int mid=(l+r)/2;
    if(L<=mid) query1(l,mid,rt*2);
    if(R>mid) query1(mid+1,r,rt*2+1);
}
int main()
{

    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    while(t--)
    {
        scanf("%d%d",&L,&R);
        big=-1,small=100000000;///每次初始化最值
        query1(1,n,1);

        printf("%d\n",big-small);///最值相减
    }
    return 0;
}

View Code

士兵杀敌（三）

相关推荐