当前位置:首页 > 开发 > 编程语言 > Java > 正文

线段树入门学习(二)(兼解POJ3468) JAVA

发表于: 2012-11-30   作者:128kj   来源:转载   浏览:
摘要: 继续上文 http://128kj.iteye.com/blog/1738772:    在那里用链状结构实现了二叉线段树,下面程序使用一维数组以完全二叉树的方式来存储。 先看一维数组存储线段树到底需要开多大的数组,网上有一个计算程序: import java.util.Scanner; /*线段树空间计算程序 Power By:Comzyh*/
继续上文 http://128kj.iteye.com/blog/1738772
   在那里用链状结构实现了二叉线段树,下面程序使用一维数组以完全二叉树的方式来存储。

先看一维数组存储线段树到底需要开多大的数组,网上有一个计算程序:
import java.util.Scanner;
/*线段树空间计算程序 Power By:Comzyh*/

 class  segment {//线段树节点
       int b,e;
 }

  public class SegmentTree{//线段树,用数组实现
   static int M=5000000;
   segment seg[];
  
   int Nnode;//节点数
   int LastNode;//最后一个节点
    
    public SegmentTree(){
      seg=new segment[M];
      for(int i=0;i<M;i++)
          seg[i]=new segment();
    }

    
   void build(int b, int e, int root){//构造线段树
     Nnode++;
     if (root>LastNode)
        LastNode=root;
     seg[root].b=b;
     seg[root].e=e;
     if (b==e)
         return;
     int mid =(b+e)>>1;
     build(b,mid,root<<1);
     build(mid+1,e,(root<<1)+1);
   }

   public int getNnode(){
      return Nnode;
   }

   public int getLastNode(){
     return LastNode;
   }

   public static void main(String args[]){
    Scanner in=new Scanner(System.in);
    int N;
    while (true){
          System.out.printf("请输入区间长度:\n");
          N=in.nextInt();
          if (N==0) break;
          SegmentTree st=new SegmentTree();
          st.build(1,N,1);
          System.out.printf("线段树构造完成, 共有%d 节点,最后一个节点是: %d\n",st.getNnode(),st.getLastNode());
          //注意:节点个数总是2N-1
           }
    }
}


运行:
C:\ex>java  SegmentTree
请输入区间长度:
5
线段树构造完成, 共有9 节点,最后一个节点是: 9
请输入区间长度:
10
线段树构造完成, 共有19 节点,最后一个节点是: 25
请输入区间长度:
100000
线段树构造完成, 共有199999 节点,最后一个节点是: 262141

对下面的程序,数组开到300000就可以了。

例:POJ3468

大致题意:给出一个长度为n的整数序列。在这个序列上有两个操作。
其中:
“C a b c”表示区间[a,b]里的所有数都增加c。

“Q a b”表示求出区间[a,b]里的所有数的和。

思路: 线段树+lazy思想:
样例:
Sample Input

10 5  
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

下面是AC过的代码:
import java.util.Scanner;
import java.io.BufferedInputStream; 
   class Tree{  //线段树节点
        int l, r;  
        long v, add;  
    } 
 public class Main{//数组实现的二叉线段树

    static int N= 100005;  
    Tree node[]=new Tree[N*3];   
    long sum[];
   

     public Main(long[] sum){
       this.sum=sum;
       for(int i=0;i<3*N;i++)
           node[i]=new Tree();
     }

  

    public int L(int u){
        return u << 1;
    }

     public int R(int u) {
      return  u << 1 | 1 ;
    }
      
   public void build ( int u, int l, int r )  //建以r为根的线段树[l,r]
    {  
        node[u].l = l;  
        node[u].r = r;  
        node[u].add = 0;  
        node[u].v = sum[r] - sum[l-1];  
        if ( l == r ) return;  
        int mid = ( l + r ) >> 1;  
        build ( L(u), l, mid );  
        build ( R(u), mid+1, r );  
    }  
      
    public void update ( int u, int l, int r, int val )  //更新
    {  
        if ( l == node[u].l && node[u].r == r )  
        {  
            node[u].add += val;  
            node[u].v += val * ( r - l + 1 );  
            return;  
        }  
      
        if ( node[u].add != 0 )  
        {  
            node[L(u)].add += node[u].add;  
            node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 );  
            node[R(u)].add += node[u].add;  
            node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 );  
            node[u].add = 0;  
        }  
      
        int mid = ( node[u].l + node[u].r ) >> 1;  
        if ( r <= mid )  
            update ( L(u), l, r, val );  
        else if ( l > mid )  
            update ( R(u), l, r, val );  
        else  
        {  
            update ( L(u), l, mid, val );  
            update ( R(u), mid+1, r, val );  
        }  
        node[u].v = node[L(u)].v + node[R(u)].v;  
    }  
      
    public long query ( int u, int l, int r )  //查询
    {  
        if ( l == node[u].l && node[u].r == r )  
            return node[u].v;  
      
        if ( node[u].add != 0 )  
        {  
            node[L(u)].add += node[u].add;  
            node[L(u)].v += node[u].add * ( node[L(u)].r - node[L(u)].l + 1 );  
            node[R(u)].add += node[u].add;  
            node[R(u)].v += node[u].add * ( node[R(u)].r - node[R(u)].l + 1 );  
            node[u].add = 0;  
        }  
      
        int mid = ( node[u].l + node[u].r ) >> 1;  // 计算左右子结点的分隔点
        if ( r <= mid)  
            return query ( L(u), l, r );  // 和左孩子有交集,考察左子结点
        else if ( l > mid )  
            return query ( R(u), l, r );  // 和右孩子有交集,考察右子结点
        else  
            return query ( L(u), l, mid ) + query ( R(u), mid+1, r );  
    }  
     public static void main(String args[]){

        Scanner in = new Scanner(new BufferedInputStream(System.in));  

          
            int n = in.nextInt();  
            int m = in.nextInt();  
            
            long[] sum=new long[n+1];
            for(int i = 1; i<=n; i++){
              sum[i] = sum[i-1] + in.nextInt();
            }
                 
            Main st=new Main(sum);
            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(1,x,y,c);  
                }  
            }  

      }    
         
    }  
   


样例2:

10 22
1 2 3 4 5 6 7 8 9 10
Q 4 4
C 1 10 3
C 6 10 3
C 6 9 3
C 8 9 -100
C 7 9 3
C 7 10 3
C 1 10 3
Q 6 10
Q 6 9
Q 8 9
Q 7 9
Q 7 10
Q 1 10
Q 2 4
C 3 6 3
Q 9 9
Q 1 1
Q 5 5
Q 6 6
Q 7 7
Q 6 8

ans

4
-82
-104
-147
-122
-100
-37
27
-73
7
14
21
25
-28

源码下载:

线段树入门学习(二)(兼解POJ3468) JAVA

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段
继续上文"线段树入门学习(二)" http://128kj.iteye.com/blog/1739064 请先看题POJ1823: 旅馆有三种
线段树的入门级 总结 转载于:http://blog.csdn.net/x314542916/article/details/7837276 真正的入
线段树的入门级 总结 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每
从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,
线段树(interval tree) 是把区间逐次二分得到的一树状结构,它反映了包括归并排序在内的很多分治算
 树结构的基本思想是分割,普通 二叉搜索树是按照数据来划分(想了解二叉搜索树的请移步: Here),
从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,
这里从一个问题引入: 在自然数,且所有的数不大于30000的范围内讨论一个问题:现在已知n条线段,把
引用Wiki对线段树的介绍: 线段树(Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号