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

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

阅读更多
继续上文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

源码下载:
  • 大小: 5.4 KB
0
0
分享到:
评论

相关推荐

    线段树入门学习(三)懒操作(兼解POJ1823) JAVA

    在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...

    线段树练习POJ 3264

    线段树的基本思想是将数组或序列分成多个部分(通常是二分),每个部分对应线段树的一个节点,通过节点间的合并操作,快速获取区间信息。 线段树的构建通常分为两个阶段:初始化和构造。初始化时,我们将原始数组中...

    学习凸包(五):卷包裹算法--兼解POJ1113(JAVA)

    在本文中,我们将深入探讨“学习凸包(五):卷包裹算法——兼解POJ1113(JAVA)”这一主题。凸包是计算机图形学、算法和数据结构领域中的一个重要概念,它指的是在一组点集中,由这些点构成的最小外接多边形。在解决...

    POJ3468.zip_poj3468

    标题中的"POJ3468.zip_poj3468"显然与编程竞赛相关,POJ(Problemset Online Judge)是北京大学主办的一个在线编程竞赛平台,其中的3468是一个具体的题目编号。这个题目可能涉及到编程挑战,要求参赛者解决特定的...

    POJ3468.zip_ACM

    标题中的"POJ3468.zip_ACM"暗示了这是一个与ACM(国际大学生程序设计竞赛)相关的项目。在ACM比赛中,参赛者需要解决各种算法问题,以提高编程和解决问题的能力。"POJ3468"是这个特定问题的编号,在编程竞赛平台上的...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    POJ 1751 求最小生成树prim算法(JAVA)

    标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...

    二维树状数组学习之二:练习POJ 1195

    在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    破解poj

    破解poj

    poj2823.cpp.tar.gz_线段树

    在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...

    poj1001java biginteger

    用java的biginteger实现的poj1001,比较简单的方法

    使用字典树和Hashtable两种方法解POJ 2503(JAVA)

    标题中的“使用字典树和Hashtable两种方法解POJ 2503”是指通过这两种数据结构解决一个特定的编程问题。POJ是Programming Online Judge的缩写,它是一个在线的编程竞赛平台,用户可以提交代码来解决特定的算法问题。...

    POJ2528-Mayor's posters【区间映射压缩(离散化)+线段树】

    POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========&gt; 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    凸包练习: POJ 2187(JAVA)

    总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...

    北大poj JAVA源码

    【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...

    字典树练习 POJ 1056

    标题中的“字典树练习 POJ 1056”是指一个编程问题,源自编程竞赛网站POJ(Programming Online Judge)的题目1056。POJ是一个在线平台,程序员可以在这里提交代码并测试其正确性,以解决给定的问题。这类问题通常...

Global site tag (gtag.js) - Google Analytics