线段树

 1 //线段树的节点
 2 //节点包括两部分信息，基本域，和信息域
 3 //基本域：左右边界ld,rd.  左右孩子：lc,rc
 4 //信息域：key值，如RMQ问题中，信息域中存储的是区间最大值
 5 struct Node{
 6     int ld,rd;
 7     Node *lc,*rc;
 8     int key;
 9 };
10  
11 //空树的建立，内含key值的初始化；
12 //一般在主函数中首先调用 Node* root= buildtree(1,n);建立一棵新树
13 Node *buildtree(int a,int b){
14     Node * p=new Node;//给P申请一块内存
15     p->ld=a;
16     p->rd=b;
17     //{初始化 p->key }
18     if(a==b)return p;//叶子节点
19     p->lc=buildtree(a,(a+b)/2);
20     p->rc=buildtree((a+b)/2+1,b);
21     return p;
22 }
23  
24 void insert(Node *T,int a,int b,int key){
25     if(a<=T->ld&&b>=T->rd){
26         //{根据key处理T->key; 然后 return ;}
27     }
28     if(a<=(T->ld+T->rd)/2)
29         insert(T->lc,a,b,key);
30     if(b>(T->ld+T->rd)/2)
31         insert(T->rc,a,b,key);
32     //{根据T->lc和T->rc的信息处理T->key}  (此处类似于归并排序中最后的合并操作)
33 }
34  
35 int search(Node *T,int a,int b){
36     int res;
37     if(a<=T->ld&&b>=T->rd)
38         // {根据T->key处理res;return res;}
39     if(a<=(T->ld+T->rd)/2)
40         //{根据search(T->lc,a,b)处理res}
41     if(b>(T->ld+T->rd)/2)
42         //根据search(T->rc,a,b)处理res}
43     return res;
44 }

模板：

基础线段树是一些基本操作之间的组合：

基本操作：单点更新、单点查询、区间更新，区间求和、区间最值

1、单点增减，区间求和

http://acm.hdu.edu.cn/showproblem.php?pid=1166

 1 View Code 
 2 
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #define MAXN 500000
 7 using namespace std;
 8 struct SegTree
 9 {
10     int left,right;
11     int anssum;
12 }tree[MAXN<<2];
13 void build(int root,int a,int b)
14 {
15     tree[root].left=a;
16     tree[root].right=b;
17     tree[root].anssum=0;
18     if(a<b)
19     {
20         int M=(a+b)>>1;
21         build(root<<1,a,M);
22         build(root<<1|1,M+1,b);
23     }
24 }
25 void update(int root,int i,int e)//单点增减
26 {
27     int L,M,R;
28     L=tree[root].left;
29     R=tree[root].right;
30     tree[root].anssum+=e;
31     if(L==R) return ;
32     M=(L+R)>>1;
33     if(i<=M)
34         update(root<<1,i,e);
35     else
36         update(root<<1|1,i,e);
37 }
38 int query(int root,int a,int b)//区间求和
39 {
40     int L,M,R;
41     L=tree[root].left;
42     R=tree[root].right;
43     M=(L+R)>>1;
44     if(a==L&&b==R)
45         return tree[root].anssum;
46     if(b<=M) return query(root<<1,a,b);
47     else if(a>M) return query(root<<1|1,a,b);
48     else return query(root<<1,a,M)+query(root<<1|1,M+1,b);
49 }
50 int main()
51 {
52     int test,n,i,a,b,k=1;
53     char s[5];
54     scanf("%d",&test);
55     while(test--)
56     {
57         scanf("%d",&n);
58         build(1,1,n);
59         for(i=1;i<=n;i++)
60         {
61             scanf("%d",&a);
62             update(1,i,a);
63         }
64         printf("Case %d:\n",k++);
65         while(scanf("%s",s)&&strcmp(s,"End")!=0)
66         {
67             scanf("%d %d",&a,&b);
68             if(s[0]=='Q') printf("%d\n",query(1,a,b));
69             else if(s[0]=='A') update(1,a,b);
70             else update(1,a,-b);
71         }
72     }
73     return 0;
74 }

2、区间更新、单点访问

http://acm.nyist.net/JudgeOnline/problem.php?pid=123

View Code 

#include<algorithm>
#include<cstring>
#include<cstdio>
#define MAXN 1000000
using namespace std;
struct SegTree
{
    int left,right;
    int acount;
} tree[MAXN<<2];
void build(int root,int a,int b)
{
    tree[root].left=a;
    tree[root].right=b;
    tree[root].acount=0;
    if(a<b)
    {
        int M=(a+b)>>1;
        build(root<<1,a,M);
        build(root<<1|1,M+1,b);
    }
}
void update(int root,int a,int b,int c)//区间更新
{
    if(a<=tree[root].left&&tree[root].right<=b)
    {
        tree[root].acount+=c;
        return ;
    }
    int M=(tree[root].left+tree[root].right)>>1;
    if(b<=M) update(root<<1,a,b,c);
    else if(a>M) update(root<<1|1,a,b,c);
    else
    {
        update(root<<1,a,M,c);
        update(root<<1|1,M+1,b,c);
    }
}
int query(int root,int a)//单点访问
{
    int cnt=tree[root].acount;
    int M=(tree[root].left+tree[root].right)>>1;
    if(tree[root].left==tree[root].right) return cnt;
    if(a<=M)  cnt+=query(root<<1,a);
    else cnt+=query(root<<1|1,a);
    return cnt;
}
int main()
{
    int n,m,a,b,c,i;
    char str[10];//这里被坑了str[5]
    scanf("%d%d",&m,&n);
    build(1,1,n);
    for(i=1; i<=m; i++)
    {
        scanf("%s",str);
        if(str[0]=='A')
        {
            scanf("%d%d%d",&a,&b,&c);
            update(1,a,b,c);
        }
        else
        {
            scanf("%d",&a);
            printf("%d\n",query(1,a));
        }
    }
    return 0;
}

3、单点替换、区间最值

http://acm.hdu.edu.cn/showproblem.php?pid=1754

 1 View Code 
 2 
 3 #include<iostream>
 4 #include<cstdio>
 5 #define MAXN 200000
 6 using namespace std;
 7 struct segtree
 8 {
 9     int left,right;
10     int ansmax;
11 }tree[MAXN<<2];
12 void build(int root,int a,int b)
13 {
14     tree[root].left=a;
15     tree[root].right=b;
16     tree[root].ansmax=0;
17     if(a<b)
18     {
19         int M=(tree[root].left+tree[root].right)>>1;
20         build(root<<1,a,M);
21         build(root<<1|1,M+1,b);
22     }
23 }
24 void update(int root,int i,int e)
25 {
26     tree[root].ansmax=max(tree[root].ansmax,e);
27     if(tree[root].left==tree[root].right) return ;
28     int M=(tree[root].left+tree[root].right)>>1;
29     if(i<=M) update(root<<1,i,e);
30     else update(root<<1|1,i,e);
31 }
32 int query(int root,int a,int b)
33 {
34     if(tree[root].left==a&&tree[root].right==b)
35     {
36         return tree[root].ansmax;
37     }
38     int M=(tree[root].left+tree[root].right)>>1;
39     if(b<=M) return query(root<<1,a,b);
40     else if(a>M) return query(root<<1|1,a,b);
41     else  return max(query(root<<1,a,M),query(root<<1|1,M+1,b));
42 }
43 int main()
44 {
45     char s;
46     int n,m,a,b,i;
47     while(scanf("%d%d",&n,&m)==2)
48     {
49         build(1,1,n);
50         for(i=1;i<=n;i++)
51         {
52             scanf("%d",&a);
53             update(1,i,a);
54         }
55         for(i=1;i<=m;i++)
56         {
57             scanf("%s%d%d",&s,&a,&b);
58             if(s=='U') update(1,a,b);
59             else printf("%d\n",query(1,a,b));
60         }
61     }
62     return 0;
63 }

注：单点增减、区间最值（update使用自底向上的方式有点慢）

 1 View Code 
 2 
 3 #include<iostream>
 4 #include<cstdio>
 5 #define MAXN 200000
 6 using namespace std;
 7 struct segtree
 8 {
 9     int left,right;
10     int ansmax;
11 }tree[MAXN<<2];
12 void build(int root,int a,int b)
13 {
14     tree[root].left=a;
15     tree[root].right=b;
16     tree[root].ansmax=0;
17     if(a<b)
18     {
19         int M=(tree[root].left+tree[root].right)>>1;
20         build(root<<1,a,M);
21         build(root<<1|1,M+1,b);
22     }
23 }
24 void update(int root,int i,int e)
25 {
26     tree[root].ansmax=max(tree[root].ansmax,e);
27     if(tree[root].left==tree[root].right) return ;
28     int M=(tree[root].left+tree[root].right)>>1;
29     if(i<=M) update(root<<1,i,e);
30     else update(root<<1|1,i,e);
31 }
32 int query(int root,int a,int b)
33 {
34     if(tree[root].left==a&&tree[root].right==b)
35     {
36         return tree[root].ansmax;
37     }
38     int M=(tree[root].left+tree[root].right)>>1;
39     if(b<=M) return query(root<<1,a,b);
40     else if(a>M) return query(root<<1|1,a,b);
41     else  return max(query(root<<1,a,M),query(root<<1|1,M+1,b));
42 }
43 int main()
44 {
45     char s;
46     int n,m,a,b,i;
47     while(scanf("%d%d",&n,&m)==2)
48     {
49         build(1,1,n);
50         for(i=1;i<=n;i++)
51         {
52             scanf("%d",&a);
53             update(1,i,a);
54         }
55         for(i=1;i<=m;i++)
56         {
57             scanf("%s%d%d",&s,&a,&b);
58             if(s=='U') update(1,a,b);
59             else printf("%d\n",query(1,a,b));
60         }
61     }
62     return 0;
63 }