`

线段树（一）——概念和应用

 
阅读更多

一、线段树概念

从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
线段树有三种基本操作: build(), update() , query() . 前两个会改变数据结构 ，后一个不影响数据结构 。
只有PushUp()操作引起数据结构的改变，而只有在build()和update()时候才会调用PushUp()，所以线段树大体上是静态，但在"建立build()"和"更新update()"时是动态的 !

      接着回到线段树上来，线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。


注意：1. 图中标注数字在实际应用中均作为下标使用! 例如sum[1,2, ... , 10]

         2. 本图中的线段树是表示的是连续 的范围；若表示离散的范围，则父亲i范围为[a,b]（a<b，否则a=b没有儿子），左儿子i*2范围为[a,(a+b)/2]，右儿子i*2+1范围为[(a+b)/2+1,b]

         3. 节点序号i从1开始（根节点为1），这样才能保证“父亲序号i的，左儿子序号为i*2，右儿子序号为i*2+1”！

             如果根节点序号为0，OMG！

 

图一就是一棵长度范围为[1 , 10]的（连续）线段树。

空间复杂度 ：长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。

update()操作 ：线段树支持最基本的操作为插入和删除一条线段。下面以插入为例详细叙述，删除类似。
将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果b>mid，那么将线段[a , b] 也插入到p的右儿子结点中。 插入（删除）操作的时间复杂度为O （ Log n ）。
 
上面都是基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。

标记 ：最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。 另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。

 

 

       参见“http://andyzh1314.ycool.com/post.1050703.html”

 

二、线段树举例

参见“http://www.notonlysuccess.com/index.php/segment-tree-complete/ ”，有很多例子

 

1. 单点更新

    敌兵布阵--> http://acm.hdu.edu.cn/showproblem.php?pid=1166

#include <stdio.h>
#define lson l , m , rt << 1
//预定义lson为： l,m,rt<<1
//——凡是写lson的地方，替换为l,m,rt<<1，表示原节点的左儿子
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 55555;
int sum[maxn<<2];

void PushUP(int rt) {
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	//sum[rt]=sum[rt/2]+sum[rt/2+1];
}

/*
	最外层调用build(1,n,1)：
	下标1为根的子树表示线段范围是[1,n]，且为离散型（整数点）
*/
void build(int l,int r,int rt) {
	//递归结束条件：到达线段树叶子节点（编号rt），则可以输入其值
	if (l == r) {
		scanf("%d",&sum[rt]);   //之所以将rt作为输入，目的是在构造叶子节点的时候要用
		return ;
	}

	int m = (l + r) >> 1;
	build(lson);	//build(l,m,rt<<1);
	build(rson);	//build(m+1,r,rt<<1|1);
	PushUP(rt);
}

//线段树（单点/非区间）更新
void update(int p,int add,int l,int r,int rt) {
	if (l == r) {
		sum[rt] += add;
		return ;
	}

	//下面采用分治法(之所以从中间劈开是为了逐渐减小问题规模)
	int m = (l + r) >> 1;
	if (p <= m) update(p , add , lson);	//#define lson l m rt<<1
	else update(p , add , rson);		//#define rson m+1 r rt<<1|1

	//回溯返回时，更新上层节点
	PushUP(rt);
}

//线段树查询
/*
	query a b对应
	query(a,b,1,n,1)
*/
int query(int L,int R,int l,int r,int rt) {
	//递归结束条件：查询范围 比 线段子树范围宽
	if (L <= l && r <= R) {
		return sum[rt];
	}

	int m = (l + r) >> 1;
	int ret = 0;
	
	//下面采用分治法(从中间劈开是为了逐渐减小问题规模)
        //注：L<=m表示查询的范围在左儿子中“有”；R>m表示查询的范围在右儿子中“有”！
        if (L <= m) ret += query(L , R , lson);	//#define lson l m rt<<1
	if (R > m) ret += query(L , R , rson);	//#define rson m+1 r rt<<1|1
	return ret;
}


int main() {
	int T , n;//T组数据，N个营地
	scanf("%d",&T);
	for (int cas = 1 ; cas <= T ; cas ++) {
		printf("Case %d:\n",cas);
		scanf("%d",&n);
		build(1 , n , 1);
		//注意：根节点编号为1，然后从左到右、从上到下编号。这样，左儿子编号=rt<<1, 右儿子编号=rt<<1|1;
		//build(1,n,1)的结果将是：以标号1(param3)为根的子树的叶节点分别对应sum[1],sum[2],sum[3],...sum[n](n=10)；
		//且构建的这棵树的每个内部节点i的sum[i]均为它所在子树的所有叶节点∑sum[j](j为叶节点编号)

		char op[10];
		while (scanf("%s",op)) {
			if (op[0] == 'E') break;

			int a , b;
			scanf("%d%d",&a,&b);
			if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));	//查询区间[a,b]，总区间[1,n]，树根1
			else if (op[0] == 'S') update(a , -b , 1 , n , 1);	//单点a, 增量-b, 总区间[1,n]，树根1
			else update(a , b , 1 , n , 1);						//单点a, 增量 b, 总区间[1,n]，树根1
		}
	}
	return 0;
}
 

同类题目：I Hate It-->http://acm.hdu.edu.cn/showproblem.php?pid=1754

 

 

 

2. 成段更新

 

重点 ：延迟标记 理解：

 

    下面这段话给了我灵感inspiration，但稍显晦涩（http://blog.sina.com.cn/s/blog_80e4822f0100yr96.html）

    对于线段树，在进行插线问线时（而树状数组不可以进行插线问线，它可以进行插线问点、插点问线，速度要比线段树快的多）通常都是采用延迟标记法，这种方法可以消除父区间对子区间的影响，也就是每次插线时，把插线节点的父节点及其父节点的父节点的sum都做相应的改变，即使每个节点的sum表示为其所覆盖区间的元素总和，查询时把父节点的delta（表示该区间每个元素的增加量）传给其左右孩子，同时把该节点的delta的变为0，消除对子节点影响。


    Sam's精解：

    延迟标记 ( 下例中add[]）反应了对线段树多次操作的前后关联。当某一次update()或query()时，程序流程沿线段树从上向下，检测所有节点的延迟标记add：

    （1）若add>0（有效）, 则表示以前某些update()操作修改了当前节点（当前节点是纯色节点）的数据结构后，就没有继续向下更新了。若本次流程需要继续沿树向下则需要完成被延迟的操作PushDown().

    （2）若add=0（无效），则表示当前节点没有被延迟的操作，无需PushDown().

 

 

    A Simple Problem with Integers --> http://poj.org/problem?id=3468

    *下面“灰底 ”部分为与单点更新的区别（对单点更新的扩充）

 

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
const int maxn = 111111;
LL add[maxn<<2];//延迟标记：当前区间的值。为了减少更新时复杂度
LL sum[maxn<<2];

void PushUp(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

 

//延迟标记从子树根下推1次（树根为rt，子树表示区间的长度为m）
void PushDown(int rt,int m) {
    //1. add[rt]的值表示：节点rt对应线段区间中所有元线段的增量
    //2. 如果当前结点有延迟标志，则向下推送，然后置0
    if (add[rt]) {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];

        sum[rt<<1] += add[rt] * (m - (m >> 1)); //左儿子rt<<1对应线段区间[1,m>>1]的长度
        sum[rt<<1|1] += add[rt] * (m >> 1);     //右儿子rt<<1|1对应线段区间[m>>1|1,m]的长度

        add[rt] = 0;
    }
}

//build()同单点更新!
void build(int l,int r,int rt) {
    add[rt] = 0;
    if (l == r) {
        scanf("%lld",&sum[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUp(rt);
}


///////////////////////////////////////////////////////////////////////////////////////////

//用户需要将区间[L,R]内所有元线段都+c

//在子树[l,r](rt为根)去更新
void update(int L,int R,int c,int l,int r,int rt) {

    if (L <= l && r <= R) {
        add[rt] += c;     //A. 查询时，只有那些线段区间内所有元线段都要被更新的结点（不必再每次调用update()时就更新到“元线段”结点）才有add[i]+=c；其他结点add[j]=0
        sum[rt] += (LL)c * (r - l + 1);
        return ;
    }

    PushDown(rt , r - l + 1);


    int m = (l + r) >> 1;   //试探更新的区间二分为两端[l,m], [m+1,r]
    if (L <= m) update(L , R , c , lson);
    if (m < R) update(L , R , c , rson);

    PushUp(rt);
}

 

//用户需要查询区间[L,R]

//在子树[l,r](rt为根)去查询

LL query(int L,int R,int l,int r,int rt) {
    if (L <= l && r <= R) {
        return sum[rt];
    }

    PushDown(rt , r - l + 1);      //B. 当查询到某个范围时，如果之前没有更新到“结点rt”以下的结点，才向下更新所有“以rt为根子树中的结点的add[i]和sum[i]”。这样做为了加快update()速度

    //询问一段，才去查询一段的值(通过if类判定)
    int m = (l + r) >> 1;
    LL ret = 0;
    if (L <= m) ret += query(L , R , lson);    //[l,m]，包含m
    if (m < R) ret += query(L , R , rson);     //(m,r]

    return ret;
}

int main() {
    int N , Q;
    scanf("%d%d",&N,&Q);
    build(1 , N , 1);
    while (Q --) {
        char op[2];
        int a , b , c;
        scanf("%s",op);
        if (op[0] == 'Q') {
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a , b , 1 , N , 1));
            //1. %lld 对应long long的十进制
            //2. query(a,b,1,N,1) 前2个参数是查询问题，后3个参数指定线段树的范围
        } else {
            scanf("%d%d%d",&a,&b,&c);
            update(a , b , c , 1 , N , 1);
        }
    }
    return 0;
}

 

3. 区间合并

这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并：

      3中情况（这是动态规划的思想/子问题结构）

                     （1）最长区间在rt的左子树中；

                     （2）最长区间在rt的右子树中；

                     （3）最长区间取 “rt左子树‘贴着她的右端点’的区间”+“rt右子树‘贴着她的左端点’的区间”

 

hotel -->http://poj.org/problem?id=3667

#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l,m,rt<<1			//#define后面没有逗号%>_<%
#define rson m+1,r,rt<<1|1

const int maxn=55555;
int lsum[maxn<<2];	//rt为根的子树中，左端点“抵拢”最左边的 最长区间长度
int rsum[maxn<<2];	//rt为根的子树中，右端点“抵拢”最右边的 最长区间长度
int msum[maxn<<2];	//rt为根的子树中最长区间长度
int cover[maxn<<2]; //延迟标记，这里初始化为-1；cover[rt]=1，开房；cover[rt]=0，退房

//下推延迟标记
//心得：延迟标记和节点上其他域没有本质差别，在下推时都要处理。
          （1）延迟标记：下推后，本节点清空（置初始状态）
          （2）其他域：下推后，本节点不作其他处理
void PushDown(int rt,int m){
	if(cover[rt]!=-1){//存在延迟标记，则进入（此时有两种延迟标记： cover[rt]=0或者 cover[rt]=1）
		cover[rt<<1]=cover[rt<<1|1]=cover[rt];
		
		msum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=cover[rt]?	0	:	m-(m>>1);
										//cover[rt]=1，开房，这些房间被占用，因此用“0”
										//cover[rt]=0，退房，这些房间被空出，因此用m-(m>>1)
		msum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=cover[rt]?	0	:	(m>>1);
										//同上理
		cover[rt]=-1;//恢复延迟标记初始值
	}
}

void PushUp(int rt, int m){
	lsum[rt]=lsum[rt<<1];
	if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];

	rsum[rt]=rsum[rt<<1|1];
	if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];

	msum[rt]=max( rsum[rt<<1]+lsum[rt<<1|1],		//左子树的最右边着色区间+右子树的最左边着色区间
					max( 
							msum[rt<<1],			//左子树
							msum[rt<<1|1]			//右子树
			                       )
                               );
}

void build(int l,int r,int rt){
	msum[rt]=lsum[rt]=rsum[rt]=r-l+1;
	cover[rt]=-1;	//cover[rt]==-1没有延迟标记； cover[rt]有两种延迟标记 0 或 1
	
	if(l==r) return;
	int m=(l+r)>>1;
	build(lson);
	build(rson);
}

void update(int L,int R,int c, int l, int r, int rt){
	if(L<=l && r<=R){
		msum[rt]=lsum[rt]=rsum[rt]=(c?0:r-l+1);//若c≠0，则用0；若c==0，则用r-l+1
		//c=1，开房，故最长区间变为0；c=0，退房，最长区间恢复为r-l+1

		cover[rt]=c;//结点所在子树的所有叶节点的增量
		return;
	}

	PushDown(rt,r-l+1);

	int m=(l+r)>>1;
	if(L<=m) update(L,R,c, lson);
	if(m<R) update(L,R,c,rson);

	PushUp(rt,r-l+1);
}

//顶层调用前， if(msum[1]<a) puts("0");
//保证query()一定能查询到合适的区间
int query(int w, int l, int r, int rt){
	if(l==r) return l;

	PushDown(rt, r-l+1);

	int m=(l+r)>>1;
	if(msum[rt<<1]>=w) 							//在左子树中找到合适的区间
		return query(w,lson);
	else if( rsum[rt<<1]+lsum[rt<<1|1]>=w )		//合适的区间跨越左右子树
		return m-rsum[rt<<1]+1;
	else										//在右子树中找到合适的区间
		return query(w,rson);
}

//先query()再update()，因此保证了所有update()均为有效的更新
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--){
		int op,a,b;
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&a);
			if(msum[1]<a) puts("0");
			else{
				int p=query(a,1,n,1);
				//在(1,n,1)对应子树中查询长度为a的区间
				//返回有效区间的起始位置

				printf("%d\n",p);

				//***开房***
				update(p,p+a-1,1, 1,n,1);//在整个线段树（1,n,1)中更新(p,p+a-1,1)
			}
		}else{
			scanf("%d%d",&a,&b);

			//***退房***
			update(a,a+b-1,0, 1,n,1);
		}
	}
	return 0;
}
 

 

4. 扫描线


Atlantis面积合并 --> http://acm.hdu.edu.cn/showproblem.php?pid=1542

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 2222;
int cnt[maxn << 2];		//对于rt，若cnt[rt]>0，则对应子树的线段区间被完全覆盖；若cnt[rt]==0，则被部分覆盖/完全没有覆盖
double sum[maxn << 2];	//对于rt,sum[rt]为对应子树覆盖的到线段区间的长度
double X[maxn];			//所有矩形的左右边界“直线”（每个矩形有两条这种直线，分别占用本数组的两个元素）

//（矩形）上/下边界“线段”
struct Seg {
	double h , l , r;	//h高度, l左端点, r右端点
	int s;	//s==1为下边界线段； s==-1为上边界线段
	Seg(){}
	Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}

	//需要按照上/下边界线段的高度来排序
	bool operator < (const Seg &cmp) const {//看运算符重载???
		return h < cmp.h;
	}
}ss[maxn];

void PushUp(int rt,int l,int r) {
	if (cnt[rt]) sum[rt] = X[r+1] - X[l];		//子树rt的线段区间完全覆盖			
	else sum[rt] = sum[rt<<1] + sum[rt<<1|1];	//子树rt的线段区间没有完全覆盖（没有覆盖/部分覆盖）
}

//需要插入/移出线段树的“上/下边界线段”： 左端点X[L], 右端点X[R+1], c==1下边界/c==-1上边界
//待插入/移除的线段树子树范围
void update(int L,int R,int c,int l,int r,int rt) {
	if (L <= l && r <= R) {
		cnt[rt] += c;
		PushUp(rt , l , r);
		return ;
	}

	int m = (l + r) >> 1;
	if (L <= m) update(L , R , c , lson);
	if (m < R) update(L , R , c , rson);

	PushUp(rt , l , r);
}
int Bin(double key,int n,double X[]) {
	int l = 0 , r = n - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		//1. 第1个分支是“递归终止条件”
		if (X[m] == key) return m;
		//2. 第2、3个分支是“二分后的两个子问题”
		if (X[m] < key) l = m + 1;
		else r = m - 1;
	}
	return -1;
}

int main() {
	int n , cas = 1;
	while (~scanf("%d",&n) && n) {
		int m = 0;
		while (n --) {
			double a , b , c , d;
			scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
			X[m] = a;
			ss[m++] = Seg(a , c , b , 1);
			X[m] = c;
			ss[m++] = Seg(a , c , d , -1);
		}
		sort(X , X + m);
		sort(ss , ss + m);

		//X[]已经递增排序后，如下操作使得X[]中不等的数字依次放在靠前
		//例如X[]={1,2,2,5,5,7} --> X[]={1,2,5,7,5,7}
		//处理后，其中X[0, ... ,k-1]为不等的数字
		int k = 1;
		for (int i = 1 ; i < m ; i ++) {
			if (X[i] != X[i-1]) X[k++] = X[i];
		}

		memset(cnt , 0 , sizeof(cnt));
		memset(sum , 0 , sizeof(sum));

		//下面为m-1轮扫描的过程
		double ret = 0;
		for (int i = 0 ; i < m - 1 ; i ++) { //i=0-->m-2
			int l = Bin(ss[i].l , k , X);
			int r = Bin(ss[i].r , k , X) - 1;

			//“上/下边界线段”长度不为0时，采取更新线段树。否则，这种“上/下边界线段”横向收缩为一个点
			if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);

			//每轮扫描：更新线段树后，累计本轮扫描新增的面积大小
			ret += sum[1] * (ss[i+1].h - ss[i].h);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret);
	}
	return 0;
}
 

 

 

  • 大小: 21.4 KB
  • 大小: 139.9 KB
  • 大小: 50.8 KB
  • 大小: 53.5 KB
分享到：
| 并查集及举例
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    统计的力量——线段树全接触_张昆玮.pptx

    通过张昆玮老师的PPT，我们不仅了解了线段树的基本概念和应用，还深入探讨了其背后的原理和技术细节。线段树作为一种强大的数据结构，在算法竞赛和实际问题解决中发挥着重要作用。通过对线段树的学习和掌握，可以...

    线段树（模板+例题——郭神）

    ### 线段树（Segment Tree）：概念与应用 #### 一、线段树的基本概念 线段树，有时也被称为区间树，是一种高效的数据结构，主要用于处理区间查询和区间更新的问题。它通过将一个大的区间划分为若干个较小的、互不...

    线段树算法的Python实现及应用介绍

    内容概要：本文详细介绍了一种高级数据结构——线段树（Segment Tree），主要探讨了它的实现方法及其在区间查询与更新问题中的应用，包括具体实现的Python代码片段。 适合人群：对数据结构有基本认识的程序员或数据...

    线段树的论文,相当的好.不过是英文的,

    本文将深入探讨线段树的概念，特别是其动态版本——**动态线段树**（Dynamic Segment Tree），以及一种创新的数据结构——**并集复制结构**(Union-Copy Structure)，该结构为动态线段树的实现提供了坚实的基础。...

    解决动态统计问题的两把利刃——剖析线段树与矩形切割_薛矛.ppt

    线段树作为一种高级数据结构，广泛应用于解决动态统计问题，尤其是在处理区间查询和修改操作时。为了适应各种复杂场景，需要对其进行适当的优化和改进，以确保在满足功能需求的同时，保持高效的性能。矩形切割可能...

    线段树资料

    #### 一、线段树的基本概念与特征 线段树是一种用于处理区间查询和更新问题的数据结构。它通过构建一颗具有特定结构的二叉树来实现对区间数据的有效管理和操作。具体而言，线段树能够高效地支持区间上的查询（如...

    ACM培训课件_提高篇_ACM算法讲座-线段树

    #### 一、线段树概念与作用 线段树是一种高效的数据结构，用于存储和处理连续区间上的数据。它通过将区间分割成若干子区间，并在树的节点上存储这些子区间的相关信息，从而能够快速地执行查询和更新操作。线段树在...

    Segment tree Beats!.pdf

    —— 深入探索高级线段树应用 #### 一、引言 在计算机科学领域，特别是在算法设计与分析方面，**线段树**是一种非常重要的数据结构，它能够高效地支持区间查询和更新操作。本文档主要介绍了线段树在解决特定类型...

    统计的力量——清华大学张昆玮

    清华大学张昆玮在其分享中深入探讨了线段树的概念、性质以及应用场景，特别强调了非递归线段树写法的重要性，并与递归写法进行了比较。线段树是一种数据结构，主要用于一维空间上的区间统计问题，并且可以推广到高维...

    5线段的比——小学生ppt学习课件

    ### 5线段的比——小学生PPT学习课件知识点详解 #### 一、相似图形的概念及线段比的基础 **相似图形定义：** - **全等形与相似形的区别：** 全等形指的是两个图形能完全重合，即它们的形状和大小完全相同；而相似...

    刷题算法提高阶段-数据结构4

    本主题“刷题算法提高阶段-数据结构4”将着重于一个特殊的数据结构——线段树，它是处理区间查询和更新问题的有效工具。线段树是一种树形数据结构，用于高效地维护一段连续区间的信息，如区间求和、查找最值等操作。...

    ACM算法与程序设计（九）1

    【ACM算法与程序设计（九）1】主要讲解了两种高级数据结构——线段树和树状数组，以及它们在解决区间动态查询问题中的应用。线段树是一种用于高效处理区间信息的数据结构，尤其适合处理区间内的修改和查询操作。 1....

    史上最简单的平衡树——无旋Treap.pdf

    - **线段树**：一种用于快速查询区间信息的数据结构，通常与懒惰传播（Lazy Propagation）一起使用，以支持区间更新操作。 - **Treap**：一种自平衡的二叉搜索树，结合了堆的性质和二叉搜索树的性质。 - **Splay ...

    第七单元《数学广角——植树问题）.doc

    《数学广角——植树问题》是小学数学课程中一个重要的单元，主要目的是引导学生通过解决实际情境中的植树问题，理解并掌握线性间隔与植树数量之间的关系，培养他们的逻辑推理能力和应用数学模型解决实际问题的能力。...

    部编第七单元 数学广角——植树问题.doc

    1. 植树问题：植树问题是一类应用数学原理解决的实际问题，通常涉及到在一定长度的线路上种植树木，其中涉及到树木的数量、间隔距离和总长度之间的关系。 2. 中间都要种：这是植树问题的一种常见类型，指的是在每两...

Magicbox
Global site tag (gtag.js) - Google Analytics