线段树入门学习(兼解HDU1754) - 心中的利剑：HTML5 Canvas游戏动画（JavaScript） - ITeye技术网站

线段树入门学习(兼解HDU1754) - 心中的利剑：HTML5 Canvas游戏动画（JavaScript） - ITeye技术网站
   线段树也叫区间树，顾名思义，线段树是一种基于区间的树，每个节点表示一个"线段"或"区间"。树的根节点表示是"整体"的区间，左右子树分别表示这个区间的左半边和右半边。

假设要构造一个表示N个区间大小的线段树，线段树的根节点表示区间[0,N-1]，然后将区间分成两半，分别为左右子树表示，这样的线段树的节点只有2N-1个，是O(N)级别的，如图所示表示构造区间[1-5]的线段树。 

 
线段树可以使用链状结构动态构造，这样的优点是节省空间，空间复杂度在2N，但是缺点就是编程复杂度大，执行效率低； 

所以线段树一般是使用一维数组以完全二叉树的方式来存储，类似堆，这样的编程复杂度低，执行效率高，但是耗费空间，一般来讲，这样情况下都是申请4N的空间.


例： HDU1754 
  很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 


Input 
本题目包含多组测试，请处理到文件结束。 
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。 
学生ID编号分别从1编到N。 

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。 
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 
Output 
对于每一次询问操作，在一行里面输出最高成绩。 
Sample Input 
5 6 
1 2 3 4 5 
Q 1 5 
U 3 6 
Q 3 4 
Q 4 5 
U 2 9 
Q 1 5 
Sample Output 
5 
6 
5 
9 

1. class Tree {  //线段树节点，  
2.     public Tree L, R;    
3.     public int ValueL, ValueR;    
4.     public int maxscore;    
5. }   
6.     static int score[] = new int[200010];    
7.   
8.     static class IntervalTree {  //线段树，链式实现  
9.             public int pos;    
10.             public Tree nodes[] = new Tree[400010];    
11.             public IntervalTree()    
12.             {    
13.                 for (int j = 0; j < 400010; j++) {    
14.                     nodes[j] = new Tree();  //所有节点先构建  
15.                 }    
16.             }    
17.   
18.             public Tree Build(int L, int R)  //建树  
19.             {    
20.                 Tree rootTree = nodes[pos++];    
21.                 rootTree.ValueL = L;    
22.                 rootTree.ValueR = R;    
23.                 if (L == R) {    
24.                    rootTree.maxscore = Math.max(score[L], score[R]);    
25.                     return rootTree;    
26.                 } else {    
27.                     int mid;    
28.                     mid = (L+R)/2;    
29.                     rootTree.L = Build(L, mid);    
30.                     rootTree.R = Build(mid+1, R);    
31.                  rootTree.maxscore = Math.max(rootTree.L.maxscore, rootTree.R.maxscore);    
32.                 }    
33.                 return rootTree;    
34.             }    
35.                 
36.             public int Query(Tree root, int LL, int RR)  //查询  
37.             {    
38.                 int ret = 0;    
39.                 if (LL == root.ValueL && RR == root.ValueR) {    
40.                     return root.maxscore;    
41.                 } else {    
42.                     int mid;    
43.                     mid = (root.ValueL+root.ValueR)/2;    
44.                     if (RR <= mid)     
45.                         ret = Query(root.L, LL, RR);    
46.                     else if (LL > mid)    
47.                      ret = Query(root.R, LL, RR);    
48.                     else    
49.                      ret = Math.max(Query(root.L, LL, mid), Query(root.R, mid + 1, RR));    
50.                     return ret;    
51.                 }    
52.             }    
53.                 
54.             public int Update(Tree root, int RR, int value) {  //更新  
55.                 int ret = 0;   
56.                 int  mid = (root.ValueL + root.ValueR)/2;     
57.                 if (RR == root.ValueL && RR == root.ValueR) {    
58.                     return root.maxscore = value;    
59.                 }  
60.                       
61.                     if (RR <= mid)     
62.                         ret = Update(root.L,  RR, value);    
63.                     else   
64.                         ret = Update(root.R,  RR, value);    
65.                      
66.                    root.maxscore= Math.max(root.maxscore,ret);    
67.                      
68.                     return root.maxscore;    
69.           }   
70.   
71.            //中序遍历二叉线段树     
72.             private void printTree(Tree root) {     
73.               if( root!= null ){     
74.                 printTree( root.L);     
75.                 System.out.print("["+root.ValueL+","+root.ValueR+"] ");     
76.                 printTree( root.R );     
77.               }   
78.                      
79.             }     
80.                
81.         }  

http://128kj.iteye.com/blog/1739064
在那里用链状结构实现了二叉线段树，下面程序使用一维数组以完全二叉树的方式来存储。 
POJ3468 

大致题意：给出一个长度为ｎ的整数序列。在这个序列上有两个操作。 
其中: 
“Ｃ　ａ　ｂ　ｃ”表示区间［ａ，ｂ］里的所有数都增加ｃ。 
“Ｑ　ａ　ｂ”表示求出区间［ａ，ｂ］里的所有数的和。 
思路：　线段树＋ｌａｚｙ思想： 

1. import java.io.BufferedInputStream;   
2.    class Tree{  //线段树节点  
3.         int l, r;    
4.         long v, add;    
5.     }   
6.  public class Main{//数组实现的二叉线段树  
7.   
8.     static int N= 100005;    
9.     Tree node[]=new Tree[N*3];     
10.     long sum[];  
11.      
12.   
13.      public Main(long[] sum){  
14.        this.sum=sum;  
15.        for(int i=0;i<3*N;i++)  
16.            node[i]=new Tree();  
17.      }  
18.   
19.     
20.   
21.     public int L(int u){  
22.         return u << 1;  
23.     }  
24.   
25.      public int R(int u) {  
26.       return  u << 1 | 1 ;  
27.     }  
28.         
29.    public void build ( int u, int l, int r )  //建以r为根的线段树[l,r]  
30.     {    
31.         node[u].l = l;    
32.         node[u].r = r;    
33.         node[u].add = 0;    
34.         node[u].v = sum[r] - sum[l-1];    
35.         if ( l == r ) return;    
36.         int mid = ( l + r ) >> 1;    
37.         build ( L(u), l, mid );    
38.         build ( R(u), mid+1, r );    
39.     }    
40.         
41.     public void update ( int u, int l, int r, int val )  //更新  
42.     {    
43.         if ( l == node[u].l && node[u].r == r )    
44.         {    
45.             node[u].add += val;    
46.             node[u].v += val * ( r - l + 1 );    
47.             return;    
48.         }    
49.         
50.         if ( node[u].add != 0 )    
51.         {    
52.             node[L(u)].add += node[u].add;    
53.             node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 );    
54.             node[R(u)].add += node[u].add;    
55.             node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 );    
56.             node[u].add = 0;    
57.         }    
58.         
59.         int mid = ( node[u].l + node[u].r ) >> 1;    
60.         if ( r <= mid )    
61.             update ( L(u), l, r, val );    
62.         else if ( l > mid )    
63.             update ( R(u), l, r, val );    
64.         else    
65.         {    
66.             update ( L(u), l, mid, val );    
67.             update ( R(u), mid+1, r, val );    
68.         }    
69.         node[u].v = node[L(u)].v + node[R(u)].v;    
70.     }    
71.         
72.     public long query ( int u, int l, int r )  //查询  
73.     {    
74.         if ( l == node[u].l && node[u].r == r )    
75.             return node[u].v;    
76.         
77.         if ( node[u].add != 0 )    
78.         {    
79.             node[L(u)].add += node[u].add;    
80.             node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 );    
81.             node[R(u)].add += node[u].add;    
82.             node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 );    
83.             node[u].add = 0;    
84.         }    
85.         
86.         int mid = ( node[u].l + node[u].r ) >> 1;  // 计算左右子结点的分隔点  
87.         if ( r <= mid)    
88.             return query ( L(u), l, r );  // 和左孩子有交集，考察左子结点  
89.         else if ( l > mid )    
90.             return query ( R(u), l, r );  // 和右孩子有交集，考察右子结点  
91.         else    
92.             return query ( L(u), l, mid ) + query ( R(u), mid+1, r );    
93.     }    
94.      public static void main(String args[]){  
95.   
96.         Scanner in = new Scanner(new BufferedInputStream(System.in));    
97.   
98.             
99.             int n = in.nextInt();    
100.             int m = in.nextInt();    
101.               
102.             long[] sum=new long[n+1];  
103.             for(int i = 1; i<=n; i++){  
104.               sum[i] = sum[i-1] + in.nextInt();  
105.             }  
106.                    
107.             Main st=new Main(sum);  
108.             st.build(1,1,n);  
109.             //st.printTree(1);  
110.             String cmd;  
111.             int x;  
112.             int y;  
113.             int c;  
114.             for(int i = 0; i<m; i++)    
115.             {    
116.                 cmd = in.next();    
117.                 if (cmd.equals("Q")) {    
118.                  x = in.nextInt();    
119.                  y = in.nextInt();       
120.                  System.out.println(st.query(1,x, y));    
121.                 } else {    
122.                     x = in.nextInt();    
123.                     y = in.nextInt();       
124.                     c=in.nextInt();    
125.                    // System.out.println("c="+c);  
126.                     st.update(1,x,y,c);    
127.                 }    
128.             }    
129.   
130.       }      
131.            
132.     }    

http://www.java3z.com/cwbwebhome/article/article1/1365.html?id=4772

class  Tree{ //线段树节点类
        int left;
        int right; 
        long sum;
        long add; 
    } 
  public class Main{
    static int  M= 300009;//节点个数
    int a[]; 
    Tree[] tree=new Tree[M];//所有节点
    public Main(int[] a){
      this.a=a;
      for(int i=0;i< M;i++)
         tree[i]=new Tree();
    }
     public int Mid(int a,int b){//求中点
       return (a+b)>>1;
    }
 
    
    /* 
     * 建树 
     * */ 
    void build(int id,int left,int right){ //以id为根建线段树
        tree[id].left=left; 
        tree[id].right=right; 
        if(left==right){ 
            tree[id].sum=a[left]; 
            tree[id].add=0; 
            return; 
        } 
        int mid=Mid(left,right); 
        build(id*2,left,mid); //建左树
        build(id*2+1,mid+1,right); //建右树
        tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; 
    } 
     
     //中序遍历以i为根二叉线段树   
            private void printTree(int i) {
             if( tree[i].left!=0 ){   
                printTree(2*i);   
                System.out.print("["+tree[i].left+","+tree[i].right+"] ");   
                printTree(2*i+1);   
              }   
       
            }  
    //懒操作
    void push_down(int id){ //需要的时候更新id节点保存的和sum,并把更新标记下传到子节点
       if(tree[id].add!=0){ //需要更新
                tree[id*2].add+=tree[id].add; 
                tree[id*2].sum += tree[id].add * ( tree[2*id].right - tree[2*id].left + 1 );    
                tree[id*2+1].add+=tree[id].add; 
                tree[id*2+1].sum+=tree[id].add * ( tree[2*id+1].right - tree[2*id+1].left + 1 );    
           tree[id].add=0; 
        } 
    } 
   
    /* 
     * 更新区间：把区间[left,right]同时增加key 
     * */ 
    void update_add(int id,int left,int right,int key){ 
      
       
        if(tree[id].left==left&&tree[id].right==right){//找到操作区间了 
            tree[id].add+=key; //标记
            tree[id].sum+=key*(right-left+1);
            return; 
        } 
        push_down(id); 
        int mid=Mid(tree[id].left,tree[id].right); 
        if(right<=mid){ 
            update_add(id*2,left,right,key); 
        }else if(left>mid){ 
            update_add(id*2+1,left,right,key); 
        }else{ 
            update_add(id*2,left,mid,key); 
            update_add(id*2+1,mid+1,right,key); 
        } 
        tree[id].sum=tree[id*2].sum+tree[2*id+1].sum;//更新父节点
    } 
    /* 
     * 查询区间 
     * */ 
    long query(int id,int left,int right){ 
      
        
        if(tree[id].left==left&&tree[id].right==right){ 
            return tree[id].sum;
        } 
         push_down(id); //先更新此节点,并把更新标记传到子节点
        int mid=Mid(tree[id].left,tree[id].right); 
        if(right<=mid){ 
            return query(id*2,left,right); 
        }else if(left>mid){ 
            return query(id*2+1,left,right); 
        }else{ 
            return query(id*2,left,mid)+query(id*2+1,mid+1,right); 
        } 
    } 
      public static void main(String args[]){
        Scanner in = new Scanner(new BufferedInputStream(System.in));  
          
            int n = in.nextInt();  
            int m = in.nextInt();  
          
            int[] a=new int[n+1];
            for(int i = 1; i<=n; i++)  
                a[i] = in.nextInt();  
            Main st=new Main(a);
            st.build(1,1,n);
            st.printTree(1);
            String cmd;
            int x;
            int y;
            int c;
            for(int i = 0; i < m; i++)  
            {  
                 cmd = in.next();  
                if (cmd.equals("Q")) {  
                 x = in.nextInt();  
                 y = in.nextInt();     
                 System.out.println(st.query(1,x, y));  
                } else {  
                    x = in.nextInt();  
                    y = in.nextInt();     
                    c=in.nextInt();  
                   // System.out.println("c="+c);
                    st.update_add(1,x,y,c);  
                }  
            }  
          
         
    }  
  }

Read full article from 线段树入门学习(兼解HDU1754) - 心中的利剑：HTML5 Canvas游戏动画（JavaScript） - ITeye技术网站