`
128kj
  • 浏览: 580675 次
  • 来自: ...
社区版块
存档分类
最新评论

线段树入门学习(兼解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);  
                }  
            }  
        }  
    }  
} 


源码下载:
  • 大小: 10.6 KB
1
0
分享到:
评论
1 楼 befairy 2012-11-30  
看见母校的题目了,呵呵。。

相关推荐

Global site tag (gtag.js) - Google Analytics