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

一维数组存储线段树要开多大的数组?

发表于: 2012-12-07   作者:128kj   来源:转载   浏览:
摘要: import java.util.Scanner; /*线段树空间计算程序 Power By:Comzyh*/ class segment {//线段树节点 int b,e; } public class SegmentTree{//线段树,用数组实现 static int M=5000000;
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

源码:

一维数组存储线段树要开多大的数组?

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一:树状数组 树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。
这几天在网上看了很多关于线段树和树状数组的资料,感觉是很重要的数据结构,有必要边学边做下记录
PS:直接看黑体字和图片吧 线段树(segment tree) 从一个问题说起吧,(HDOJ1166) 给定一个数列A1
一维线段树组 树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。
第一种方法 import java.util.Arrays; public class Test { /** * @param args */ public static vo
一 问题:假设有一个一维整型数组,随机化这个数组,即使得每个元素在数组中随机出现,且概率一样。
/* * 程序的版权和版本声明部分 * Copyright (c)2012, 烟台大学计算机学院学生 * All rightsreserve
foreach遍历数组 <?php /* * 数组的遍历 */ $language = array("French",'German','Russian','Ch
数组初始化: 1,动态初始化:数组定义与为数组分配空间和赋值的操作分开进行 2,静态初始化;在定
题意: 同上 题解: 抓着这题作死的搞~~是因为今天练习赛的一道题.SPOJ KQUERY.直到我用最后一种树状
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号