线段树入门学习(兼解HDU1754)

先看网上的介绍：
   线段树也叫区间树，顾名思义，线段树是一种基于区间的树，每个节点表示一个“线段”或“区间”。树的根节点表示是“整体”的区间，左右子树分别表示这个区间的左半边和右半边。

基本结构及性质

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





1）存储：

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

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

2）基本操作：

   线段树支持的操作有：构造，插入，查找，更新，删除；这些操作不一定都有，在实现上也不一定都是一个套路，这都取决于实际问题；实际上，通过在线段树节点上记录不同的信息，线段树可以完成很多不同的任务；线段树的高度为logn，这也就使得线段树可以在O(lgn)的时间完成插入、查询、删除等操作。


例： 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

下面是AC过的代码：

import java.io.*;  
import java.util.*;  
  
class Tree {  //线段树节点，
    public Tree L, R;  
    public int ValueL, ValueR;  
    public int maxscore;  
}

 
  
public class Main {  
    static int score[] = new int[200010];  

    static class IntervalTree {  //线段树，链式实现
            public int pos;  
            public Tree nodes[] = new Tree[400010];  
            public IntervalTree()  
            {  
                for (int j = 0; j < 400010; j++) {  
                    nodes[j] = new Tree();  //所有节点先构建
                }  
            }  

            public Tree Build(int L, int R)  //建树
            {  
                Tree rootTree = nodes[pos++];  
                rootTree.ValueL = L;  
                rootTree.ValueR = R;  
                if (L == R) {  
                   rootTree.maxscore = Math.max(score[L], score[R]);  
                    return rootTree;  
                } else {  
                    int mid;  
                    mid = (L+R)/2;  
                    rootTree.L = Build(L, mid);  
                    rootTree.R = Build(mid+1, R);  
                 rootTree.maxscore = Math.max(rootTree.L.maxscore, rootTree.R.maxscore);  
                }  
                return rootTree;  
            }  
              
            public int Query(Tree root, int LL, int RR)  //查询
            {  
                int ret = 0;  
                if (LL == root.ValueL && RR == root.ValueR) {  
                    return root.maxscore;  
                } else {  
                    int mid;  
                    mid = (root.ValueL+root.ValueR)/2;  
                    if (RR <= mid)   
                        ret = Query(root.L, LL, RR);  
                    else if (LL > mid)  
                     ret = Query(root.R, LL, RR);  
                    else  
                     ret = Math.max(Query(root.L, LL, mid), Query(root.R, mid + 1, RR));  
                    return ret;  
                }  
            }  
              
            public int Update(Tree root, int RR, int value) {  //更新
                int ret = 0; 
                int  mid = (root.ValueL + root.ValueR)/2;   
                if (RR == root.ValueL && RR == root.ValueR) {  
                    return root.maxscore = value;  
                }
                    
                    if (RR <= mid)   
                        ret = Update(root.L,  RR, value);  
                    else 
                        ret = Update(root.R,  RR, value);  
                   
                   root.maxscore= Math.max(root.maxscore,ret);  
                   
                    return root.maxscore;  
          } 

           //中序遍历二叉线段树   
            private void printTree(Tree root) {   
              if( root!= null ){   
                printTree( root.L);   
                System.out.print("["+root.ValueL+","+root.ValueR+"] ");   
                printTree( root.R );   
              } 
                   
            }   
             
        }

    public static void main(String[] args) throws IOException  
    {  
       
        int n, m;  
        int a, b;  
        int i;  
        IntervalTree iTree = new IntervalTree();  
        Tree rootTree;  
        String cmd;  
        Scanner cin = new Scanner(new BufferedInputStream(System.in));  
        while (cin.hasNext())   
        {  
            n = cin.nextInt();  
            m = cin.nextInt();  
            for(i = 1; i<=n; i++)  
                score[i] = cin.nextInt();  
            iTree.pos = 0;  
            rootTree = iTree.Build(1, n);  
            //iTree.printTree(rootTree);
          //  System.out.println();
            for(i = 0; i<m; i++)  
            {  
                cmd = cin.next();  
                a = cin.nextInt();  
                b = cin.nextInt();  
                if (cmd.equals("Q")) {  
                  if(a == b)  
                        System.out.println(score[a]);  
                  else  
                   System.out.println(iTree.Query(rootTree, a, b));  
                } else {  
                    score[a] = b;  
                    iTree.Update(rootTree, a, b);  
                }  
            }  
        }  
    }  
} 

源码下载：

评论

1 楼 befairy 2012-11-30  

看见母校的题目了，呵呵。。