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
源码:
分享到:
相关推荐
一维数组转二维数组
一维数组是基本的数组,多维数组是在一维数组的基础上创建的。一维数组的创建过程如下。 (1)创建数组框架。在前面板窗口控件选板中选择控件“新式→数组、矩阵与簇→数组,置于前面板窗口的空白处,如图1所示。...
用C++语音实现一维数组二维数组写入txt,从txt中读取数据存到一维数组、二维数组,数组用指针表示
将labview内二维数组方便的转化为一维数组使用
C# json 一维数组 和 二维数组的转换 写的非常详细,对大家有帮助
采集到一维数组后,通过平均值方式实现滤波
介绍了数组、一维数组、二维数组、多维数组及其应用示例
使用Excel两个一维数组构造二维数组.rar,本例所示的Sheet1工作表已经定义了两个一维数组,利用公式对这连个数组进行加法运算,可以生成一个新的二维数组。
用二维数组实现二维矩阵的加法和乘法 #include #define SIZE 4 void addMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void mulMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void ...
matlab 三维 数组 在 MATLAB 中,三维数组是一种特殊的矩阵,它是由一系列具有相同数据类型的三维矩阵组成...但是,三维数组的维度较大,存储和处理数据的效率较低,因此在实际应用中需要根据具体情况进行选择和使用。
自己做老师时整理出来的一维数组题目,可用于教学、测试、面试题,需要的拿走
用数据结构与算法 实现的数组 用一维数组定义用 二维数组 定义三维数组 用模版
【输出形式】程序将两个有序一维数组合并为一个有序数组并按照从小到大顺序输出。每个元素输出时用空格分隔,最后一个输出之后没有空格。 【样例输入】 6 2 5 8 11 20 35 4 1 6 15 60 【样例输出】1 2 5 6 8 11 15 ...
数组应用——一维数组排序; 定义一组无序的整型数列,共10个数值,经过一定的处理,使该数组由大到小排列,并输出到屏幕上。具体要求如下: 定义int型数组arrayorder并赋初值为0,长度为10,以承载该数列; 使用...
matlab 三维 数组 matlab创建三维数组的三种方法 matlab创建三维数组的三种方法 matlab创建三维数组的三种方法 matlab创建三维数组的三种方法 matlab创建三维数组的三种方法 matlab创建三维数组的三种方法 matlab...
public class Test { // 二维数组冒泡排序 public static void main... //一维数组的长度(二维数组的列*宽) System.out.println("原始二维数组:"); //打印原始二维数组 for(i=0;i;i++) { for(j=0;j;j++) {
将时间序列年月日型的三维数组数据转换为单列,本程序运行生态水文模型IHA而编制,亦适用于其他三维数据的转换。
PHP实现一维数组的组合算法,欢迎下载和评论。
几个Excel vba示例文件. 包括行列转置,表格数据到数组,一维数组转二维数组,单列转多列等。均含示例数据,如: 250B的文本测试数据,晶振微调后的频率测试数据等。 另外还有EXCEL的常用命令语句精选。