奥门威尼斯网址树状数组和线段树的总结

先说树状数组吧 主要有lowbit,update,getsum

在已知了树状数组的使用方法,那么便可以用它来解决一些实际问题了,比如说下面一道经典题:敌兵布阵
:HDU:1166。
题目大致意图为:敌方有排好的数个阵营,每个阵营都有一些士兵,且不断有人进出,在某个时刻快速统计阵营号在某个范围内的阵营内人数和。
为了快速统计前n项和且尽量减少统计时间,避免所有的数据遍历,很容易想到树状数组的应用,不但可以以很少的时间更新数组,而且计算和时减少遍历求和时间,假设要求的阵营排号范围为(a,b),那么只需要sum(b)-sum(a-1),即可,我们可以按照此思路很容易地写出相关的代码:

奥门威尼斯网址,Crayon

Time Limit: 2000/1000MS (Java/Others) Memory
Limit: 
128000/64000KB (Java/Others)

SubmitStatus

题目网址:

线段树经验及总结,线段树经验总结

 

一开始学线段树是跟zhx老师,用一个sum数组代替结构体

但是发现sum数组比较难打lazy标记,而且调试非常非常困难

所以就跟着xxy老师用struct结构体存变量

感觉这种方式虽然比sum难写一点但是比较容易理解

 

到现在线段树的基本操作:

1.单点修改

2.单点查询

3.区间修改(加减)

4.区间查询

基本都掌握了,但是像区间加减乘除混合的听别人说太高大上而且时间比较急就仅仅看看了思路,没手动实践

 

在敲线段树的时候总结出了一点规律和经验:

1.结构体的大小必须要开4*MAXN

2.所有的中间值m都是由当前树的左右区间决定的(建树例外)

  也就是m=(tree[k].l+tree[k].r)/2;

  而不是m=(ll+rr)/2;

  但是建树的时候一定要按照后者写!

3.在进行标记下传的时候所有操作全部是+=,而不是=  !

4.在判断区间的时候必须按照

  if(tree[k].l>=ll&&tree[k].r<=rr)

 的格式写,否则容易造成判断错误

5.在判断要查询的区间的时候必须按照

    if(ll<=m)    interval_change(k*2,ll,rr,v);
    if(rr>m)    interval_change(k*2+1,ll,rr,v);

  的格式写,否则容易出错!

一开始学线段树是跟zhx老师,用一个sum数组代替结构体
但是发现sum数组比较难打lazy标记,而且调试非…

int lowbit(int x){    return x&(-x);}

int update(int x,int date){    while(x<=y)    {        c[x]+=date;        x+=lowbit;    }}

int getsum(int x){    int ans=0;    while(x>0)    {        ans+=c[x];        x-=lowbit;    }    return ans;}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#define lowbit(x)  (x&(-x))
#define MMAX 500010
using namespace std;

int m;
int C[MMAX];

int sum(int i)
{
    int ans=0;
    while (i>0)
    {
        ans+=C[i];
        i-=lowbit(i);
    }
    return ans;
}

void add(int num,int i)
{
    while (i<=m)
    {
        C[i]+=num;
        i+=lowbit(i);
    }
}


void main()
{
    int i,j,k,n,x,y;
    char ch[7];
    scanf("%d",&n);
    for (j=0;j<n;j++)
    {
        memset (C,0,sizeof (C));
        scanf("%d",&m);
        for (i=0;i<m;i++)
        {
            scanf("%d",&k);
            add(k,i+1);
        }
        printf("Case %d:\n",j+1);
        getchar();
        while(scanf("%s",ch)&&strcmp(ch,"End")!=0)
        {
            scanf("%d%d",&x,&y);
            if (strcmp(ch,"Add")==0)
            {
                add(y,x);
            }
            else if (strcmp(ch,"Query")==0)
            {
                printf("%d\n",sum(y)-sum(x-1));
            }
            else if (strcmp(ch,"Sub")==0)
            {
                add(-y,x);
            }
            getchar();
        }
    }
}

Problem Description

Background

奥门威尼斯网址 1

Mary love painting so much, but as we know she can’t draw very well.
There is no one appreciate her works, so she come up with a puzzle with
herself.

Description

There are only one case in each input file, the first line is a
integer N (N ≤ 1,000,00) denoted the total operations executed by
Mary.

Then following N lines, each line is one of the folling operations.

  • D L R : draw a segment [L, R], 1 ≤ L ≤  R ≤ 1,000,000,000.
  • C I : clear the ith added segment. It’s guaranteed that the
    every added segment will be cleared only once.
  • Q L R : query the number of segment sharing at least a common
    point with interval [L, R]. 1 ≤ L ≤ R ≤ 1,000,000,000.

Description

lowbit的作用就是找到该节点的父节点或子节点 图

该程序在指定的时间范围内,是可以顺利AC的,那么,我们不妨继续寻找更加简便的方法来更快的减少时间。
我们知道,树状数组的结果是前N项的和,那么,正如该题,如果我们要求的是一段范围内的和该怎么办呢?假设范围是(a,b),那么1到a-1的求和我们计算了两遍,而需要使用的却不是这段的和,我们便不由得去想,可否想一个办法让数组直接存储的就是一定范围内的和,这时候需要涉及到的就是线段树。

Input

n

Then following n operations …

As is known to all, the blooming time and duration varies between
different kinds of flowers. Now there is a garden planted full of
flowers. The gardener wants to know how many flowers will bloom in the
garden in a specific time. But there are too many flowers in the garden,
so he wants you to help him.

奥门威尼斯网址 2

顾名思义,线段树即在树的每一个节点都储存一个线段,若把线段视为一个范围,那么每一个结点都会是下标为一段范围的数组和,而叶子节点存放一个元素,如图

Output

For each query, print the result on a single line …

 

注意了 a数组存的是原来的数 c数组的意义代表着c[i] 就是前i项的和

奥门威尼斯网址 3

Sample Input

6
D 1 3
D 2 4
Q 2 3
D 2 4
C 2
Q 2 3

Input

线段树的话

ABCD代表的叶子节点只存储一个元素的和,而EF存储的是两个孩子结点的和E=A+B=1+2,F=C+D=3+4,而G结点存储的也为其两个孩子的和即G=E+F=A+B+C+D=1+2+3+4。
那么,如果想要求(3,4)的和,只需要调出F结点输出即可,如果有一个叶子节点内的数据变动,要做的便是向上迭代,将其双亲结点变动相应的参数,直到树的根结点。
但是如何准确地使用线段树呢?首先需要做的就是深刻理解线段树的原理和性质:

Sample Output

2
2

线段树

奥门威尼斯网址 4奥门威尼斯网址 5

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define ll long long
  8 typedef struct abcd
  9 {
 10     int l,r,ci,i;
 11     char x;
 12 } abcd;
 13 abcd a[110000];
 14 typedef struct abc
 15 {
 16     int x,i;
 17 } abc;
 18 abc c[300000];
 19 int cn=0,b[110000],bn=1;
 20 bool cmp(abc x,abc y)
 21 {
 22     return x.x<y.x;
 23 }
 24 bool cmp1(abcd x,abcd y)
 25 {
 26     return x.l<y.l;
 27 }
 28 bool cmp2(abcd x,abcd y)
 29 {
 30     return x.r<y.r;
 31 }
 32 bool cmp3(abcd x,abcd y)
 33 {
 34     return x.i<y.i;
 35 }
 36 typedef struct tree
 37 {
 38     int a,d,sub;
 39 } tree;
 40 tree t[600000];
 41 void fun(int x)
 42 {
 43     if(t[x].d)
 44     {
 45         t[x<<1].d+=t[x].d;
 46         t[x<<1].sub+=t[x].d;
 47         t[x<<1|1].sub+=t[x].d;
 48         t[x<<1|1].d+=t[x].d;
 49         t[x<<1].a+=t[x].d;
 50         t[x<<1|1].a+=t[x].d;
 51         t[x].d=0;
 52     }
 53 }
 54 void update(int x,int y,int b,int c,int tt,int z)
 55 {
 56     if(x<=b&&y>=c)
 57     {
 58         t[tt].sub+=z;
 59         t[tt].d+=z;
 60         t[tt].a+=z;
 61         return ;
 62     }
 63     if(t[tt].d)
 64     fun(tt);
 65     int m=(b+c)>>1;
 66     if(x<=m&&y>m)t[tt].sub+=z;
 67     if(x<=m)update(x,y,b,m,tt<<1,z);
 68     if(y>m)update(x,y,m+1,c,tt<<1|1,z);
 69     t[tt].a=t[tt<<1].a+t[tt<<1|1].a-t[tt].sub;
 70 }
 71 int query(int x,int y,int b,int c,int tt)
 72 {
 73     if(x<=b&&y>=c)
 74     {
 75         return t[tt].a;
 76     }
 77     if(t[tt].d)
 78     fun(tt);
 79     int m=(b+c)>>1;
 80     int r=0,sub;
 81     if(x<=m)r=query(x,y,b,m,tt<<1);
 82     if(y>m)r=r+query(x,y,m+1,c,tt<<1|1);
 83     t[tt].a=t[tt<<1].a+t[tt<<1|1].a-t[tt].sub;
 84     if(x<=m&&y>m)
 85         return r-t[tt].sub;
 86     else return r;
 87 }
 88 int main()
 89 {
 90     int n,i,j;
 91    //freopen("in.txt","r",stdin);
 92     scanf("%d",&n);
 93     for(i=0; i<n; i++)
 94     {
 95         getchar();
 96         scanf("%c",&a[i].x);
 97         if(a[i].x=='C')
 98         {
 99             scanf("%d",&a[i].ci);
100         }
101         else
102         {
103             scanf("%d%d",&a[i].l,&a[i].r);
104             c[cn++].x=a[i].l,c[cn++].x=a[i].r;
105             if(a[i].x=='D')
106                 b[bn++]=i;
107         }
108         a[i].i=i;
109     }
110     int now=2;
111     sort(c,c+cn,cmp);
112     c[0].i=1;
113     for(i=1; i<cn; i++)
114     {
115         if(c[i].x==c[i-1].x)
116             c[i].i=c[i-1].i;
117         else c[i].i=now++;
118     }
119 
120     sort(a,a+n,cmp1);
121     j=0;
122     for(i=0; i<n; i++)
123     {
124         while(i<n&&a[i].x=='C')i++;
125         if(i==n)break;
126         while(a[i].l!=c[j].x)j++;
127         a[i].l=c[j].i;
128     }
129     sort(a,a+n,cmp2);
130     j=0;
131     for(i=0; i<n; i++)
132     {
133         while(i<n&&a[i].x=='C')i++;
134         if(i==n)break;
135         while(a[i].r!=c[j].x)j++;
136         a[i].r=c[j].i;
137     }
138     sort(a,a+n,cmp3);
139     /*for(i=0; i<n; i++)
140         cout<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<endl;*/
141     memset(t,0,sizeof(t));
142     for(i=0; i<n; i++)
143     {
144         if(a[i].x=='D')
145         {
146             update(a[i].l,a[i].r,1,c[cn-1].i,1,1);
147         }
148         else if(a[i].x=='C')
149         {
150             update(a[b[a[i].ci]].l,a[b[a[i].ci]].r,1,c[cn-1].i,1,-1);
151         }
152         else
153         {
154             printf("%d\n",query(a[i].l,a[i].r,1,c[cn-1].i,1));
155         }
156     }
157 }

View Code

 树状数组

奥门威尼斯网址 6奥门威尼斯网址 5

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define ll long long
  8 typedef struct abcd
  9 {
 10     int l,r,ci,i;
 11     char x;
 12 } abcd;
 13 abcd a[110000];
 14 typedef struct abc
 15 {
 16     int x,i;
 17 } abc;
 18 abc c[300000];
 19 int cn=0,b[110000],bn=1;
 20 bool cmp(abc x,abc y)
 21 {
 22     return x.x<y.x;
 23 }
 24 bool cmp1(abcd x,abcd y)
 25 {
 26     return x.l<y.l;
 27 }
 28 bool cmp2(abcd x,abcd y)
 29 {
 30     return x.r<y.r;
 31 }
 32 bool cmp3(abcd x,abcd y)
 33 {
 34     return x.i<y.i;
 35 }
 36 int ab[800000][2],m;
 37 int lowbit(int x)
 38 {
 39     return x&(-x);
 40 }
 41 void update(int y,int x,int z)
 42 {
 43     while(x<=m)
 44     {
 45         ab[x][y]+=z;
 46         x+=lowbit(x);
 47     }
 48 }
 49 int query(int y,int x)
 50 {
 51     int sum=0;
 52     while(x>0)
 53     {
 54         sum+=ab[x][y];
 55         x-=lowbit(x);
 56     }
 57     return sum;
 58 }
 59 int main()
 60 {
 61     int n,i,j;
 62    // freopen("in.txt","r",stdin);
 63     scanf("%d",&n);
 64     for(i=0; i<n; i++)
 65     {
 66         getchar();
 67         scanf("%c",&a[i].x);
 68         if(a[i].x=='C')
 69         {
 70             scanf("%d",&a[i].ci);
 71         }
 72         else
 73         {
 74             scanf("%d%d",&a[i].l,&a[i].r);
 75             c[cn++].x=a[i].l,c[cn++].x=a[i].r;
 76             if(a[i].x=='D')
 77                 b[bn++]=i;
 78         }
 79         a[i].i=i;
 80     }
 81     int now=2,sum=0;
 82     sort(c,c+cn,cmp);
 83     c[0].i=1;
 84     for(i=1; i<cn; i++)
 85     {
 86         if(c[i].x==c[i-1].x)
 87             c[i].i=c[i-1].i;
 88         else c[i].i=now++;
 89     }
 90 
 91     sort(a,a+n,cmp1);
 92     j=0;
 93     for(i=0; i<n; i++)
 94     {
 95         while(i<n&&a[i].x=='C')i++;
 96         if(i==n)break;
 97         while(a[i].l!=c[j].x)j++;
 98         a[i].l=c[j].i;
 99     }
100     sort(a,a+n,cmp2);
101     j=0;
102     for(i=0; i<n; i++)
103     {
104         while(i<n&&a[i].x=='C')i++;
105         if(i==n)break;
106         while(a[i].r!=c[j].x)j++;
107         a[i].r=c[j].i;
108     }
109     sort(a,a+n,cmp3);
110     /*for(i=0; i<n; i++)
111         cout<<a[i].x<<" "<<a[i].l<<" "<<a[i].r<<endl;*/
112     m=c[cn-1].i;
113     for(i=0; i<n; i++)
114     {
115         if(a[i].x=='D')
116         {
117             update(0,a[i].l,1);
118             update(1,a[i].r,1);
119             sum++;
120         }
121         else if(a[i].x=='C')
122         {
123             update(0,a[b[a[i].ci]].l,-1);
124             update(1,a[b[a[i].ci]].r,-1);
125             sum--;
126         }
127         else
128         {
129             int ans=query(0,a[i].r);
130             ans-=query(1,a[i].l-1);
131             printf("%d\n",ans);
132         }
133     }
134 }

View Code

 

The first line contains a single integer t (1 <= t <= 10), the
number of test cases. 
For each case, the first line contains two integer N and M, where N (1
<= N <= 10^5) is the number of flowers, and M (1 <= M <=
10^5) is the query times. 
In the next N lines, each line contains two integer S i and
i (1 <= S i <= T i <= 10^9),
means i-th flower will be blooming at time [S i,
Ti]. 
In the next M lines, each line contains an integer T i, means
the time of i-th query. 

奥门威尼斯网址 8

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

 

差不多两个数组搞定一个tree和一个add

—-来自百度百科
【以下以 求区间最大值为例】
先看声明:

Output

先是建立树

01.#include <stdio.h>  
02.#include <math.h>  
03.const int MAXNODE = 2097152;  
04.const int MAX = 1000003;  
05.struct NODE{  
06.    int value;        // 结点对应区间的权值  
07.    int left,right;   // 区间 [left,right]  
08.}node[MAXNODE];  
09.int father[MAX];     // 每个点(当区间长度为0时,对应一个点)对应的结构体数组下标  

For each case, output the case number as shown and then print M lines.
Each line contains an integer, meaning the number of blooming
flowers. 
Sample outputs are available for more details. 

线段树是从1这个节点开始的

奥门威尼斯网址 9

 

void build(int l,int r,int k)//l,r为建树的范围 {    if(l==r)    {        cin>>tree[k];        return ;    }    int m=>>1;    build(l,m,k<<1);//递归建立数     build(m+1,r,k<<1|1);    tree[k]=tree[k<<1]+tree[k<<1|1];//求和 }

【创建线段树(初始化)】:

Sample Input

自我觉得这个是比较灵活的,对这个改动一下就成为不同的功能,比如最大值

由于线段树是用二叉树结构储存的,而且是近乎完全二叉树的,所以在这里我使用了数组来代替链表上图中区间上面的红色数字表示了结构体数组中对应的下标。

2 1 1 5 10 4 2 3 1 4 4 8 1 4 6

void build(int l,int r,int k){    if(l==r)    {        cin>>tree[k];        return ;    }    int m=>>1;    build(l,m,k<<1);    build(m+1,r,k<<1|1);    //tree[k]=tree[k<<1]+tree[k<<1|1];    tree[k]=max(tree[k<<1],tree[k<<1|1]); }

在完全二叉树中假如一个结点的序号(数组下标)为 I ,那么
(二叉树基本关系)

 

这样就变成了父节点 为子节点的最大值

I 的父亲为 I/2,

Sample Output

然后是点更新

I 的另一个兄弟为 I/2 * 2 或 I/2✲2+1

Case #1:

void update(int ee,int c,int l,int r,int k){    if(l==r)    {        tree[k]+=c;        //tree[k]=c;  这样就是更改这个数,而不是加         return ;    }    int m=>>1;    if update(ee,c,l,m,k<<1);//ee为需要更新的叶子节点,通过递归找     else update(ee,c,m+1,r,k<<1|1);    tree[k]=tree[k<<1]+tree[k<<1|1];}

I 的两个孩子为 I*2 (左) I✲2+1(右)

0

然后是区间更新 ,这里需要懒标记,这个确实比较难理解

有了这样的关系之后,我们便能很方便的写出创建线段树的代码了。

Case #2:

void update(int x,int y,int c,int l,int r,int k)//x,y为需要更新区间,l,r为k这一节点的管理范围 {    if(x<=l&&y>=r)    {        tree[k]=c*(r-l+1);//这一点为c乘以这一点管理的数量        add[k]=c;//把这一点标记一下,为懒标记        return;//注意是结束了     }    int m=>>1;    pushdown(k,m-l+1,r-m);//下推标记    if update(x,y,c,l,m,k<<1);    if update(x,y,c,m+1,r,k<<1|1);//注意 这里不是else 而是都要更新并查找     tree[k]=tree[k<<1]+tree[k<<1|1]; } 

void pushdown(int k,int ln,int rn)//ln,rn为左子树,右子树的数字数量。 {    if    {        add[k<<1]+=add[k];        add[k<<1|1]+=add[k];//传递这个标记                sum[k<<1]+=add[k]*ln;        sum[k<<1|1]+=add[k]*rn;        add[k]=0;    }} 
01.void BuildTree(int i,int left,int right){ // 为区间[left,right]建立一个以i为祖先的线段树,i为数组下标,我称作结点序号  
02.    node[i].left = left;    // 写入第i个结点中的 左区间  
03.    node[i].right = right;  // 写入第i个结点中的 右区间  
04.    node[i].value = 0;      // 每个区间初始化为 0  
05.    if (left == right){ // 当区间长度为 0 时,结束递归  
06.        father[left] = i; // 能知道某个点对应的序号,为了更新的时候从下往上一直到顶  
07.        return;  
08.    }  
09.    // 该结点往 左孩子的方向 继续建立线段树,线段的划分是二分思想,如果写过二分查找的话这里很容易接受  
10.    // 这里将 区间[left,right] 一分为二了  
11.    BuildTree(i<<1, left, (int)floor( (right+left) / 2.0));  
12.    // 该结点往 右孩子的方向 继续建立线段树  
13.    BuildTree((i<<1) + 1, (int)floor( (right+left) / 2.0) + 1, right);  
14.}  

1

上面是要求和的下推标记,但如果说是这道题

【单点更新线段树】:

2

POJ – 2299

假设该线段树的作用是找到N个节点的最大值,由于我事先用 father[ ]
数组保存过 每单个结点
对应的下标了,因此我只需要知道第几个点,就能知道这个点在结构体中的位置(即下标)了,这样的话,根据之前已知的基本关系,就只需要直接一路更新上去即可。

1

为这个区间都改变成一样的数,而不是相加一样的数

01.void UpdataTree(int ri){ // 从下往上更新(注:这个点本身已经在函数外更新过了)  
02.  
03.    if (ri == 1)return; // 向上已经找到了祖先(整个线段树的祖先结点 对应的下标为1)  
04.    int fi = ri / 2;        // ri 的父结点  
05.    int a = node[fi<<1].value; // 该父结点的两个孩子结点(左)  
06.    int b = node[(fi<<1)+1].value; // 右  (每个数字按位左移一个单位相当于乘2)
07.    node[fi].value = (a > b)?(a):(b);    // 更新这个父结点(从两个孩子结点中挑个大的)  
08.    UpdataTree(ri/2);       // 递归更新,由父结点往上找  
09.}  
//直到更新完毕,根节点中存放的数则是数组中所有的数组的最大数。

 

void pushdown(int k,int ln,int rn){    if{        add[k<<1]=add[k];        add[k<<1|1]=add[k];
        sum[k<<1]=add[k]*ln;        sum[k<<1|1]=add[k]*rn;        add[k]=0;    }}

【查询区间最大值】:
将一段区间按照建立的线段树从上往下一直拆开,直到存在有完全重合的区间停止。对照图例建立的树,假如查询区间为
[2,5]

题意:有n种花,给了这n种花的花期时间,Si~Ti,求在某一时间t,有多少种花正在开放。

最后是区间求和

奥门威尼斯网址 10

思路:这题给的花期时间数据为1~10^9,无法开辟这么大的数组,不能直接建树,必须先将数据进行离散化。离散化:在百科上看到一句很好的话:“离散化就是把连续的量,变成离散的量即变成一个一个的值”,例如区间(1,100)由于这是一个实数区间,其中间的值有无数个,如果我们能把它变为1到100内的整数,这样这些数就变成了有限个,即离散了;
 ,我们将每个区间的端点都存到一个数组中,然后将这些端点,按照从小到大排列(之后要去除这个数组中重复的点),并建立为与其下标的映射,然后用其下标建树,因为我们只是使用了需要的空间,并没有在整个空间上建树,这样就大大节省了空间和时间,如题中第二个例子,我们将所有数据按照从小到大排列后为1
2 3 4 6 8 分别对应下标1 2 3 4 5
6,此题数据小我们看不出明显的差别,但是如果数据中有区间(1000,10000),那差别马上就出来了,比如我们把题中的区间(4,8)换做(1000,10000)那么如果采用离散化思想,我们还是先排列大小
1 2 3 6 1000 10000对应下标1 2 3 4 5
6,我们只需建一棵根为6的树即可,如果不用离散化,我们就需要建造根为10000的树,大大浪费了空间。

int query(int x,int y,int l,int r,int k){    if(x<=l&&r<=y)    {        return tree[k];    }    int m=>>1;    pushdown(k,m+1-l,r-m);        int ans=0;    if ans+=query(x,y,l,m,k<<1);    if ans+=query(x,y,m+1,r,k<<1|1);    return ans;}

红色的区间为完全重合的区间,因为在这个具体问题中我们只需要比较这
三个区间的值 找出 最大值 即可。

然而!!!我发现同学他们的代码没有使用离散化,而是开辟了150000的空间就过了,很明显测试数据没有很大,都在150000以内,唉!所以可以不用离散化。

01.int Max = -1<<20;  
02.void Query(int i,int l,int r){ // i为区间的序号(对应的区间是最大范围的那个区间,也是第一个图最顶端的区间,一般初始是 1 啦)  
03.    if (node[i].left == l && node[i].right == r){ // 找到了一个完全重合的区间  
04.        Max = (Max < node[i].value)?node[i].value:(Max);  
05.        return ;  
06.    }  
07.    i = i << 1; // get the left child of the tree node  
08.    if (l <= node[i].right){ // 左区间有涉及  
09.        if (r <= node[i].right) // 全包含于左区间,则查询区间形态不变  
10.            Query(i, l, r);  
11.        else // 半包含于左区间,则查询区间拆分,左端点不变,右端点变为左孩子的右区间端点  
12.            Query(i, l, node[i].right);  
13.    }  
14.    i += 1; // right child of the tree  
15.    if (r >= node[i].left){ // 右区间有涉及  
16.        if (l >= node[i].left) // 全包含于右区间,则查询区间形态不变  
17.            Query(i, l, r);  
18.        else // 半包含于左区间,则查询区间拆分,与上同理  
19.            Query(i, node[i].left, r);  
20.    }  
21.}  

方法一:使用树状数组,若花期为t1~t2,更新t1-1及t1-1以下的子树根节点都减一,更新t2及t2以下的子树根节点加一,若求x时刻有多少种花正开着,将x及上方一路节点均相加,最后的和即是结果。

此段算法代码并不好理解,但是,可以根据二叉树的遍历便可以得到大致思路:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 152005
using namespace std;
int c[N];

int Lowbit(int t)
{   ///设k为t末尾0的个数,则求得为2^k=t&(t^(t-1));
    return t&(t^(t-1));
}
void update(int x,int t)
{
    while(x > 0)
    {
        c[x]+=t;
        x -= Lowbit(x);
    }
}
int sum(int li)
{
    int sum=0;
    while(li<=N)
    {
        sum+=c[li];
        li=li+Lowbit(li);
    }
    return sum;
}

int main()
{
    int T;
    int n,M,t1,t2,x,Case=1;
    scanf("%d",&T);
    while(T--)
    {
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&M);
        while(n--)
        {
            scanf("%d%d",&t1,&t2);
            update(t1-1,-1);
            update(t2,1);
        }
        printf("Case #%d:\n",Case++);
        while(M--)
        {
            scanf("%d",&x);
            printf("%d\n",sum(x));
        }
    }
    return 0;
}

首先,从最大的结点:根结点开始遍历,如果目标数据域与根数据相同,那么直接输出的就是跟数据域内的数据,如果不相同,那么一定是小于跟数据域的,可以先判断其在左子树和右子树中是不是有目标数据域内的数。
首先,判断是否在左子树中:将i从代表跟子树的下标1转换为左子树的下标i<<1;然后判断,如果在左子树中有数据,那么一定是从小的数据开始排,有if
(node[i].right>=l),如果有,那么判断是否整个数据域都在左子树中:if
(node[i].right>=r)如果是,那么就可以递归算法,传参i(左子树坐标),继续从头判断是否目标数据域全部在该结点中……如果不是,那么则说明目标数据域即在左子树中有元素,也在右子树中有,先判断左子树中的元素具体位置,将r置为node[i].right,保证目标数据域都在i结点中,递归,再次调用数据,判断是否目标数据域全部在该结点中……直到找到了左子树中的部分的最大值,那么,右子树中的该怎么办呢?已知找到后,循环将跳出,那么,将i++,得到的下标就是当前子树的兄弟,即右子树了;已知右子树可能有部分的目标数据域内的数据,也可能没有,那么,只要加以判断if
(node[i].left<=r),之后的判断与左子树内的处理相似,如果判断为否,退出循环,找到解,若为是,判断是否全部都在该区域中,递归参数i,若为否,递归数据域的左区间将为node[i].left。
此代码运用的环境为求最大值,可以减少比较和遍历时间。

方法二:使用线段树进行区间更新。

在本题当中,所求的解为一定数据域内的和,便需要找到完全符合的数据域,并将它们的值并入和的值即可。根据题意得出相应代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int Max=150005;
int N,M;
int c[Max];

struct Node
{
    int l,r;
    int cnt;
}node[5*Max];

void build(int L,int R,int i)
{
    node[i].l=L;
    node[i].r=R;
    node[i].cnt=0;
    if(L==R)  return;
    int mid=(L+R)/2;
    build(L,mid,2*i);
    build(mid+1,R,2*i+1);
}

int update(int t1,int t2,int i)
{
    if(node[i].l==t1&&node[i].r==t2)
    {
        node[i].cnt++;
        return 0;
    }
    int mid=(node[i].l+node[i].r)/2;
    if(t2<=mid) update(t1,t2,2*i);
    else if(t1>mid)  update(t1,t2,2*i+1);
    else
    {
        update(t1,mid,2*i);
        update(mid+1,t2,2*i+1);
    }
}

int chazhao(int x,int i)
{
    int sum=0;
    if(node[i].l<=x&&node[i].r>=x)
        sum+=node[i].cnt;
    if(node[i].l>x) return 0;
    if(node[i].r<x) return 0;
    sum+=chazhao(x,2*i);
    sum+=chazhao(x,2*i+1);
    return sum;
}

int main()
{
    int T,t1,t2,Case=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&M);
        build(1,Max,1);
        for(int i=1;i<=N;i++)
        {
            scanf("%d%d",&t1,&t2);
            update(t1,t2,1);
        }
        for(int i=0;i<M;i++)
        scanf("%d",&c[i]);
        printf("Case #%d:\n",Case++);
        for(int i=0;i<M;i++)
        {
            printf("%d\n",chazhao(c[i],1));
        }
    }
    return 0;
}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#define MMAX 3000010
using namespace std;

struct
{
    int value;
    int right,left;
}node[MMAX];

int num[500010];
int sum;
int n;

void build (int i,int l,int r)
{
    if (l==r)
    {
        node[i].right=r;
        node[i].left=l;
        node[i].value=num[l];
        return;
    }
    node[i].left=l;
    node[i].right=r;
    build(i*2,l,(l+r)/2);
    build(i*2+1,(l+r)/2+1,r);
    node[i].value=node[i*2].value+node[i*2+1].value;
}


void add(int i,int l,int r)
{
    if (node[i].left==l&&node[i].right==r)
    {
        sum+=node[i].value;
        return;
    }
    i=i<<1;
    if (node[i].right>=l)
    {
        if (node[i].right>=r)
            add(i,l,r);
        else
            add(i,l,node[i].right);
    }
    i++;
    if (node[i].left<=r)
    {
        if (node[i].left<=l)
            add(i,l,r);
        else
            add(i,node[i].left,r);
    }
}

void update(int i,int shu)
{
    int a=1;
    while (a<=MMAX)
    {
        node[a].value+=shu;
        if (node[a].right==node[a].left)
            break;
        if (i<=(node[a].left+node[a].right)/2)
            a*=2;
        else
            a=2*a+1;
    }
}


void main()
{
    int i,j,k,m,x,y;
    char s[12];
    scanf("%d",&m);
    for (int cas=1;cas<=m;cas++)
    {
        scanf("%d",&n);
        memset(num,0,sizeof(num));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
        }
        build(1,1,n);
        printf("Case %d:\n",cas);
        getchar();
        while(scanf("%s",s)&&s[0]!='E')
        {
            sum=0;
            scanf("%d%d",&x,&y);
            getchar();
            if (s[0]=='Q')
            {
                add(1,x,y);
                printf("%d\n",sum);
            }
            else if (s[0]=='A')
                update(x,y);
            else if (s[0]=='S')
                update(x,-y);
        }
    }
}

 

由上面的代码论述可知,实现从根结点到达某个根结点的数据更新,不但可以按照比较左右数据域的大小比较,还可以根据实际情况将其与(node[i].left+node[i].right)/2进行比较来确定目标结点在左子树中还是右子树中。

发表评论

电子邮件地址不会被公开。 必填项已用*标注