本文主要是介绍线段树入门学习(二）(兼解POJ3468) JAVA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
继续上文 http://128kj.iteye.com/blog/1738772：在那里用链状结构实现了二叉线段树，下面程序使用一维数组以完全二叉树的方式来存储。
先看一维数组存储线段树到底需要开多大的数组，网上有一个计算程序：
Java代码 
- 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
- }
- }
- }
这篇关于线段树入门学习(二）(兼解POJ3468) JAVA的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
