线段树的学习过程

敌兵布阵。

  1 #include<stdio.h>
  2 #include<string.h>
  3 #define lson l,mid,res<<1
  4 #define rson mid+1,r,res<<1|1
  5 //感谢图灵;
  6 int tree[50000*4];
  7 //res是树对应数组位置。
  8 void PushUp(int res)
  9 {
 10     tree[res] = tree[res<<1]+tree[res<<1|1];
 11 }
 12 void build(int l,int r,int res)
 13 {
 14     if(l==r)
 15     {
 16         scanf("%d",&tree[res]);
 17         return;
 18     }
 19     int mid = (l+r)>>1;
 20     build(lson);
 21     build(rson);
 22     PushUp(res);
 23 }
 24 //goal军营目标
 25 void Add(int l,int r,int res,int goal,int ad)
 26 {
 27     if(l==r)
 28     {
 29         tree[res] += ad;
 30         return;
 31     }
 32     int mid  = (l+r)>>1;
 33     if(goal<=mid)
 34     {
 35         Add(l,mid,res<<1,goal,ad);
 36     }
 37     else
 38     {
 39         Add(mid+1,r,res<<1|1,goal,ad);
 40     }
 41     PushUp(res);
 42 }
 43 void Del(int l,int r,int res,int goal,int ad)
 44 {
 45     if(l==r)
 46     {
 47         tree[res] -= ad; 
 48         return;
 49     }
 50     int mid  = (l+r)>>1;
 51     if(goal<=mid)
 52     {
 53         Del(l,mid,res<<1,goal,ad);
 54     }
 55     else
 56     {
 57         Del(mid+1,r,res<<1|1,goal,ad);
 58     }
 59     PushUp(res);
 60 }
 61 
 62 int Query(int l,int r,int res,int ll,int rr)
 63 {
 64     if(l>=ll&&r<=rr)
 65     {
 66         return tree[res];
 67     }
 68     int mid = (l+r)>>1;
 69     if(rr<=mid)
 70     {
 71         return Query(l,mid,res<<1,ll,rr);
 72     }
 73     else if(ll>mid)
 74     {
 75         return Query(mid+1,r,res<<1|1,ll,rr);
 76     }
 77     else
 78     {
 79         return (Query(l,mid,res<<1,ll,rr)+Query(mid+1,r,res<<1|1,ll,rr));
 80     }
 81     /*
 82         存在rr>r的情况。 比如 2 7 。 r = mid = 5 
 83         所以我的判断是 l>=ll r<=rr 
 84         notonlysuccess 的代码
 85         int query(int L,int R,int l,int r,int rt) {
 86         if (L <= l && r <= R) {
 87         return sum[rt];
 88         }
 89         int m = (l + r) >> 1;
 90         int ret = 0;
 91         if (L <= m) ret += query(L , R , lson);
 92         if (R > m) ret += query(L , R , rson);
 93         return ret;
 94         }
 95         利用的是分开讨论。L和R 而不是统一讨论区间L~R(这个思维不错。)
 96     */
 97 }
 98 
 99 int main()
100 {
101     int T,N,M,i,j;
102     char command[10];
103     scanf("%d",&T);
104     M = T;
105     while(T--)
106     {
107         scanf("%d",&N);
108         build(1,N,1);
109         printf("Case %d:
",M-T);
110         while(scanf("%s",command)!=EOF)
111         {
112             if(!strcmp(command,"End"))
113             {
114                 break;
115             }
116             else if(command[0]=='A')
117             {
118                 scanf("%d%d",&i,&j);
119                 Add(1,N,1,i,j);
120             }
121             else if(command[0]=='Q')
122             {
123                 scanf("%d%d",&i,&j);
124                 printf("%d
",Query(1,N,1,i,j));
125             }
126             else
127             {
128                 scanf("%d%d",&i,&j);
129                 Del(1,N,1,i,j);
130             }
131         }
132     }
133 }
134 //注意res的含义。还有函数的参数比我想象中要多

View Code

线段树求逆序数。

重点在于线段树的应用。

这里线段数的含义是在某范围内有多少个元素。

首先明确逆序数的求法是怎么求的。

所求的序列 1 3 6 9 0 8 5 7 4 2

对应的结果 1 2 4 6 0 4 2 2 1 0

resultsum = 22

线段树适用条件G：所求序列必须是相邻离散的。假如说不是。可以做上点细节处理。

比如上述序列符合条件G。

那么我们可以做以下处理。

对于1 我们开始查询当前树中有哪个元素比这个大

只要查找1~1范围上的

当然是0

更新1 所能存在的区间。

1-10 1-5 1-3 1-2 1-1

对于3 我们开始查询当前树种有哪个元素比这个大

所以只要查找1~3范围上的。对于1~3范围我们会直接到1~3 返回1.

更新3 所能存在的区间。

1-10 1-5 1-3 2-3 3-3

以此完成这个过程。

对于线段树。它是一种能让单个点变成集合的树。凡是遇到和集合有关的。也许可以使用它。

也许也有和集合无关的

杭电2795

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 //build 在需要的值处填上w  1~h键树。当h>N时范围只是N的即可,这点十分重要。（不能全部都用N建树。）
 6 //query 和 update 貌似可以在一起的
 7 // update 如果左边先符合 先去左边。否则是右边。然后改值
 8 // query 如果左边先符合的话 先去左边。 然后输出位置。
 9 int tree[200002*4];//200002*4
10 int flag;//查找得到找不到。
11 int position;
12 int w;
13 int max(int a,int b)
14 {
15     return a>b?a:b;
16 }
17 void PushUp(int rt)
18 {
19     tree[rt] = max(tree[rt<<1],tree[rt<<1|1]);
20 }
21 void build(int l,int r,int rt)
22 {
23     tree[rt] = w;
24     if(l==r){return;}
25     int mid = (l+r)>>1;
26     build(lson);
27     build(rson);    
28 }
29 //递归的处理。 别做超前操作。可以处理当前点，然后用判断进入是否后点。
30 void gets(int l,int r,int rt,int value)
31 {
32     //如果可以进来说明是满足条件的。除非是第一个点
33     //第一个不一定是初始化的W 因为会发生变化的
34     if(value>tree[rt]){return;}
35     if(l==r){flag = 1;position=l;tree[rt]-=value;return;}
36     int mid = (l+r)>>1;
37     if(value<=tree[rt<<1])
38     {
39         gets(lson,value);
40     }
41     else
42     {
43         gets(rson,value);
44     }
45     PushUp(rt);
46 }
47 
48 int main()
49 {
50     int h,n,val,t;
51     while(scanf("%d%d%d",&h,&w,&n)!=EOF)
52     {
53         t = n+1;
54         build(1,t,1);
55         while(n--)
56         {
57             flag = 0;
58             scanf("%d",&val);
59             gets(1,t,1,val);
60             if(flag)
61             {
62                 printf("%d
",position);
63             }
64             else
65             {
66                 printf("-1
");
67             }
68         }
69     }
70 }

View Code

题目本身和区间无关。但是我们可以利用区间来优化查找。

也许我该思考一下这种查找的性质

w
1 2 3 4 5 6 7 8 9 h
从左到右开始找、最小值。
区间化让符合条件的查找更加地快速。
个人感觉有着二分的效率。但是还能查找到的是最前端
并且即使不能保持着数据的顺序性。这种查找还是可行的。
好厉害的线段树。让查找区间化了。

敌兵布阵。
查询区间上的和值
I hate it
查询区间上的最值
逆序数。
查询特定区间上的和值

区间更新。LAZY标志。

说白了lazy就是令更新缓慢一步。而当你要使用该点后续的孩子的时候。就要PushDown 出于方便考虑更新会同时更新左右的孩子。

另外值得注意的是。其实本质上线段树就是必须更新上下节点的。不过一般单点更新都是在最底端。所以没有体现此处。

而如果我们更新到底。那将不会很效率。

其实我个人觉得区间更新和单点更新都能用一段代码概括。以及查找在本质上其实都是统一的。待深入讨论

先贴上hook的思绪加代码

 1 //其实更新这个操作本身就有PushUp和PushDown.
 2 //build 让所有的add为0 tree为1 默认为铜
 3 //query 和 update 在一起。
 4 //重点是lazy 标志的处理。
 5 //PushDown 写在判断终点的后面。也就是要使用后续的蒂娜了
 6 //然后更新的时候记得最后让add=0 add[]记录的是单位增量
 7 //左边和右边同时更新。这样省事多了
 8 #include<stdio.h>
 9 #include<string.h>
10 #define lson l,mid,rt<<1
11 #define rson mid+1,r,rt<<1|1
12 
13 int tree[100002*4];//11W*4
14 int add[100002*4];//11W*4
15 
16 void PushUp(int rt)
17 {
18     tree[rt] = tree[rt<<1]+tree[rt<<1|1];
19 }
20 //其实仔细想一想这个方法也很有趣
21 //m 是必须得。毕竟我不是用结构体。那么我想得到该点的范围限制
22 // l r m = r-l+1. 1~5 5-1+1=5.左边范围是1~3 3. (m+1)>>1 右边是m>>1
23 void PushDown(int rt,int m)
24 {
25     if(add[rt]>0)
26     {
27         add[rt<<1] = add[rt]; 
28         add[rt<<1|1] = add[rt];
29         tree[rt<<1] = add[rt]*((m+1)>>1);
30         tree[rt<<1|1] = add[rt]*(m>>1);
31         add[rt] = 0;
32     }    
33 }
34 void build(int l,int r,int rt)
35 {
36     add[rt] = 0;
37     tree[rt] = 1;
38     if(l==r){return;}
39     int mid = (l+r)>>1;
40     build(lson);
41     build(rson);
42 
43     PushUp(rt);
44 }
45 //让我们认为写update 和 query 不过是查找的过程而已吧
46 //单点的update是简单的 假如是区间上的 就和query 差不多了。
47 //只不过引入了lazy 来优化
48 //这个hock 最后的query 只是最大的即可.
49 void update(int l,int r,int rt,int L,int R,int Ad)
50 {
51     //终点
52     if(R>=r&&L<=l)
53     {
54         add[rt] = Ad;
55         tree[rt] = Ad*(r-l+1);
56         return;
57     }
58     //不是终点
59     PushDown(rt,r-l+1);
60     int mid = (l+r)>>1;
61     if(R<=mid)
62     {
63         update(lson,L,R,Ad);
64     }
65     else if(L>mid)
66     {
67         update(rson,L,R,Ad);
68     }
69     else //交集
70     {
71         update(lson,L,R,Ad);
72         update(rson,L,R,Ad);
73     }
74     PushUp(rt);//把孩子的效果更新上去
75 }
76 int main()
77 {
78     int T,TT,N,M,l,r,Ad;
79     scanf("%d",&T);
80     TT=T;
81     while(T--)
82     {
83         scanf("%d%d",&N,&M);
84         build(1,N,1);
85         while(M--)
86         {
87             scanf("%d%d%d",&l,&r,&Ad);
88             update(1,N,1,l,r,Ad);
89         }
90         printf("Case %d: The total value of the hook is %d.
",TT-T,tree[1]);
91     }
92 }

View Code

然后是区间求和

#include<stdio.h>
#include<string.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tree[20];//10W*4
int add[20];
void PushUp(int rt)
{
    tree[rt] = tree[rt<<1]+tree[rt<<1|1];
}
//左边是 (m+1)>>1 右边是 m>>1
void PushDown(int rt,int m)
{
    add[rt<<1] += add[rt];
    add[rt<<1|1] += add[rt];
    tree[rt<<1] +=  add[rt]*((m+1)>>1);
    tree[rt<<1|1] += add[rt]*(m>>1);
    add[rt] = 0;
}
void build(int l,int r,int rt)
{
    add[rt] = 0;
    if (l==r)
    {
        scanf("%d",&tree[rt]);
        return;
    }
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}

void update(int l,int r,int rt,int L,int R,int ad)
{
    //由于R和L 始终没有发生变化。
    //这样只影响第三种情况。
    //也就是  l mid L R  mid+1 r L R 这个时候迅速返回的
    //包含的话 就返回。否则的话。继续缩小。
    if(R>=r&&L<=l)
    {
        tree[rt] += ad*(r-l+1);
        //不能用R-L+1.
        add[rt] += ad;
        return;
    }
    PushDown(rt,r-l+1);
    int mid = (l+r)>>1;
    if(R<=mid)
    {
        update(lson,L,R,ad);
    }
    else if(L>mid)
    {
        update(rson,L,R,ad);
    }
    else
    {
        update(lson,L,R,ad);
        update(rson,L,R,ad);
    }
    PushUp(rt);
}
int query(int l,int r,int rt,int L,int R)
{
    if(R>=r&&L<=l)
    {
        return tree[rt];
    }
    PushDown(rt,r-l+1);
    int mid = (l+r)>>1;
    if(R<=mid)
    {
        return query(lson,L,R);
    }
    else if(L>mid)
    {
        return query(rson,L,R);
    }
    else
    {
        return query(lson,L,R)+query(rson,L,R);
    }
}
int main()
{
    int N,T;
    char s[10];
    int L,R,ad;
    while(scanf("%d%d",&N,&T)!=EOF)
    {
        build(1,N,1);
        while(T--)
        {
            scanf("%s",s);
            if(s[0]=='C')
            {
                scanf("%d%d%d",&L,&R,&ad);
                update(1,N,1,L,R,ad);
            }
            else
            {
                scanf("%d%d",&L,&R);
                printf("%d
",query(1,N,1,L,R));
            }
        }
    }
}
//add[] += 的问题 比如一个东西的右孩子。我们对于加法问题。
//其上一个增量会被复写掉。并且没有被使用过。

View Code

区间覆盖。

POJ 2528

离散化：

　　　　大范围数据。可是使用的数据只有几个。把使用的数据离散化映射到0~N上。为什么是0~N? 线段树的性质。来造树即可。

　　　　那么我们代码需要解决的问题就是。首先是离散化的缺陷问题。弥补掉。然后我们弄线段树更新的时候输入一个值要获得对应的映射值。

　　　　X[i] = 0~N 那么X开的区间还是要很大。所以必须是X[0~N] = i .才可以。然后输入l r 再bin查找下标即可。

　　　　那么我们可以抽象出一个Bin(int key,int X[],int m) . m为X的大小。返回坐标。

　　　　我们来做区间更新之区间覆盖问题即可。

这个问题很有意思。只用一个数组tree 搞定。对tree做的事情如同对add做的。

int tree[20];//
void PushUp(){}//->no use
void PushDown(int rt)
{
    if(tree[rt]>0)
    {
    tree[rt<<1]=tree[rt<<1|1]=tree[rt];
    tree[rt] = -1;
    }
}

View Code