线段树总结

模板：

点修改：

 1 int sum[maxn<<2], maxv[maxn<<2], minv[maxn<<2];  
 2   
 3 void maintain(int u)  
 4 {  
 5     int lc = u*2, rc = u*2+1;  
 6     sum[u] = sum[lc] + sum[rc];  
 7     maxv[u] = max(maxv[lc], maxv[rc]);  
 8     minv[u] = min(minv[lc]. minv[rc]);  
 9 }  
10   
11 void build(int u, int l, int r)  
12 {  
13     if(l==r)  
14     {  
15         sum[u] = maxv[u] = minv[u] = 0;  
16         return;  
17     }  
18       
19     int mid = (l+r)>>1;  
20     build(u*2, l, mid);  
21     build(u*2+1, mid+1, r);  
22     maintain(u);  
23 }  
24   
25 void add_val(int u,int l,int r,int x, int val)  
26 {  
27     if(l==r)  
28     {  
29         sum[u] += val;  
30         maxv[u] += val;  
31         minv[u] += val;  
32         return ;  
33     }  
34       
35     int mid = (l+r)>>1;  
36     if(x<=mid) add_val(u*2, l, mid, x, val);  
37     else add_val(u*2+1, mid+1, r, x, val);  
38     maintain(u);  
39 }  
40   
41 void set_val(int u, int l, int r, int x, int val)  
42 {  
43     if(l==r)  
44     {  
45         sum[u] = val;  
46         maxv[u] = val;  
47         minv[u] = val;  
48         return;  
49     }  
50       
51     int mid = (l+r)>>1;  
52     if(x<=mid) set_val(u*2, l, mid, x, val);  
53     else set_val(u*2+1, mid+1, r, x, val);  
54     maintain(u);  
55 }  
56   
57 int maxx, minn;   
58 int query(int u,int l, int r, int x, int y)  
59 {  
60     if(x<=l && r<=y)  
61     {  
62         maxx = max(maxx, maxv[u]);  
63         minn = min(minn, minv[u]);  
64         return sum[u];  
65     }  
66       
67     int ret = 0;  
68     int mid = (l+r)>>1;  
69     if(x<=mid) ret += query(u*2, l, mid, x, y);  
70     if(y>=mid+1) ret += query(u*2+1, mid+1, r, x ,y);  
71     return ret;  
72 }

View Code

区间修改：

  1 int sum[maxn<<2], maxv[maxn<<2], minv[maxn<<2], addv[maxn<<2], setv[maxn<<2];  
  2   
  3 void pushup(int u)  
  4 {  
  5     int l = 2*u, r = 2*u+1;  
  6     sum[u] = sum[l] + sum[r];  
  7     maxv[u] = max(maxv[l], maxv[r]);  
  8     minv[u] = min(minv[l], minv[r]);  
  9 }  
 10   
 11 void pushdown(int u, int len)  
 12 {  
 13     int lc = 2*u, rc = 2*u+1;  
 14     if(setv[u]>=0)  
 15     {  
 16         addv[lc] = addv[rc] = 0;  
 17         minv[lc] = minv[rc] = maxv[lc] = maxv[rc] = setv[u];  
 18         sum[lc] = (len+1)/2*setv[u];  
 19         sum[rc] = len/2*setv[u];  
 20         setv[lc] = setv[rc] = setv[u];  
 21         setv[u] = -1;  
 22     }  
 23   
 24     if(addv[u])  
 25     {  
 26         sum[lc] += (len+1)/2*addv[u];  
 27         sum[rc] += len/2*addv[u];  
 28         maxv[lc] += addv[u]; minv[lc] += addv[u];  
 29         maxv[rc] += addv[u]; minv[rc] += addv[u];  
 30         addv[lc] += addv[u]; addv[rc] += addv[u];  
 31         addv[u] = 0;  
 32     }  
 33 }  
 34   
 35 void build(int u, int l, int r)  
 36 {  
 37     if(l==r)  
 38     {  
 39         sum[u] = maxv[u] = minv[u] = 0;  
 40         return;  
 41     }  
 42   
 43     int mid = (l+r)>>1;  
 44     build(u*2, l, mid);  
 45     build(u*2+1, mid+1, r);  
 46     pushup(u);  
 47 }  
 48   
 49 void set_val(int u, int l, int r, int x, int y, int val)  
 50 {  
 51     if(x<=l && r<=y)  
 52     {  
 53         addv[u] = 0;  
 54         maxv[u] = minv[u] = val;  
 55         sum[u] = (r-l+1)*val;  
 56         setv[u] = val;  
 57         return;  
 58     }  
 59   
 60     pushdown(u, r-l+1);  
 61     int mid = (l+r)>>1;  
 62     if(x<=mid) set_val(u*2, l, mid, x, y, val);  
 63     if(y>=mid+1) set_val(u*2+1, mid+1, r, x, y, val);  
 64     pushup(u);  
 65 }  
 66   
 67   
 68 void add_val(int u, int l, int r, int x, int y, int val)  
 69 {  
 70     if(x<=l && r<=y)  
 71     {  
 72         maxv[u] += val;  
 73         minv[u] += val;  
 74         sum[u] += (r-l+1)*val;  
 75         addv[u] += val;  
 76         return;  
 77     }  
 78   
 79     pushdown(u, r-l+1);  
 80     int mid = (l+r)>>1;  
 81     if(x<=mid)  add_val(u*2, l, mid, x, y, val);  
 82     if(y>=mid+1) add_val(u*2+1, mid+1, r, x, y, val);  
 83     pushup(u);  
 84 }  
 85   
 86 int ansmax, ansmin;  
 87 int query(int u, int l, int r, int x, int y)  
 88 {  
 89     if(x<=l && r<=y)  
 90     {  
 91         ansmax = max(ansmax, maxv[u]);  
 92         ansmin = min(ansmin, minv[u]);  
 93         return sum[u];  
 94     }  
 95   
 96     pushdown(u, r-l+1);  
 97     int mid = (l+r)>>1;  
 98     int ret = 0;  
 99     if(x<=mid) ret += query(u*2, l, mid, x, y);  
100     if(y>=mid+1) ret += query(u*2+1, mid+1, r, x, y);  
101     return ret;  
102 }

View Code

一、点修改：

HDU1166 敌兵布阵

HDU1754 —— I Hate It

POJ3264 Balanced Lineup

二、区间修改：

HDU3974 Assign the task

POJ3468 A Simple Problem with Integers

HDU4027 Can you answer these queries?（区间开根）

CodeChef - ANDMIN （区间与&）

三、区间染色：

HDU1698 Just a Hook

ZOJ1610 Count the Colors

POJ2528 Mayor's posters

四、区间合并：

HDU1540 Tunnel Warfare

SPOJ - GSS1 （区间最大连续和）

五、连续型线段树（求面积、周长、体积）：

1.此种线段树的操作对象为连续型，即最小的元素为长度为1的区间[l,r],其中l和r只代表端点(r-l>=1)，用于确定区间的位置和长度，在l处和r处没有特别的含义。而以往做的什么单点更新以及普通的区间更新之类的，都属于离散型，他们的最小的操作对象是一个一个的点，因而在l处和r处是有含义的。

2.因为最小的操作对象为一段区间，因而线段树的写法也需要做适当变形：

void push_up(int u, int l, int r)
{
    if(times[u]>0)      //该区间被覆盖: 覆盖长度为区间长度
        sum[u] = X[r] - X[l];
    else            //该区间没有被覆盖: 如果为单位区间，则覆盖长度为0，否则为两个子区间的覆盖长度之和。
        sum[u] = (l+1==r)?0:sum[u*2]+sum[u*2+1];
}

void add(int u, int l, int r, int x, int y, int v)
{
    if(x<=l && r<=y)
    {
        times[u] += v;
        push_up(u, l, r);
        return;
    }

    int mid = (l+r)>>1;
    if(x<=mid-1) add(u*2, l, mid, x, y, v);　　//在左端至少要有一个单位区间（为[mid-1, mid]，所以x需要满足x<=mid-1）
    if(y>=mid+1) add(u*2+1, mid, r, x, y, v);　//在右端至少要有一个单位区间（为[mid, mid+1]，所以y需要满足y>=mid+1）
    push_up(u, l, r); 
}

View Code

3.为何不需要push_down()和query()函数呢？

答：因为push_down()的本质作用是把修改传递下去，以查询更小的区间的具体信息。但是对于此种类型的线段树，我们只需要获取整段的信息（即sum[1]），而不需要取查询子区间的信息，所有：当修改了某一子区间的后，只需把修改信息往上更新，而不需要理会往下的更小的子区间。因而不需要push_down()和query()函数。

HDU1542 Atlantis （矩形并面积）

HDU1255 覆盖的面积（矩形交面积）

POJ1177 Picture （矩形并周长）

HDU3642 Get The Treasury （长方体交体积）