欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线段树(C++)

程序员文章站 2022-03-21 08:27:50
...

线段树

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。

线段树(C++)

 

开原数组4倍大的空间

区间查询:询问某段区间的某些性质(极值,求和,etc)

区间更新

             更新点,查询区间

             更新区间,查询点

             更新区间,查询区间

 

对于任一非叶子节点,若该区间为[l,r],则左儿子为[l,(l+r)/2],右儿子为[(l+r)/2+1,r]

#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<map>
#include<list>
#include<iostream>
#define MAX 10000
using namespace std;
// rt << 1 = rt * 2, rt << 1 | 1 = rt * 2 + 1
int a[MAX],ans[MAX<<2],lazy[MAX<<2],n;
//a[]为原序列信息,ans[]模拟线段树维护区间和,lazy[]为懒惰标记

//向上更新节点
void pushup(int rt){
	ans[rt] = ans[rt<<1] + ans[rt<<1|1];	//查询区间和
	//ans[rt] = max(ans[rt<<1],ans[rt<<1|1]);	查询区间最值
}

//建树操作, rt记录当前位置
// build(1,n, 1)
void build(int l,int r,int rt){
	if(l == r){
		ans[rt] = a[l]; //或初始化为0
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt<<1);	//左子树递归
	build(mid+1, r, rt<<1|1);	//右子树递归
	pushup(rt);
}

//向下更新节点
//l表示节点个数
// += : 区间增减  =:区间替换
void pushdown(int rt, int l){
	if(lazy[rt]){
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1|1] += lazy[rt];
		ans[rt << 1] += lazy[rt] * (l-l/2);
		ans[rt << 1|1] += lazy[rt] * (l/2);
		lazy[rt] = 0;
	}
}

//单点更新
//L  R  区间范围
//l 查找的点
//C 更新值
void add(int L, int R, int l, int C, int rt){
	if(L == R){
		ans[rt] = C;
		return ;
	}
	int mid = (L+R) >> 1;
	pushdown(rt, R-L+1);	//若既有点更新又有区间更新,需要此句
	if(l <= mid)
		add(L, mid, l, C, rt <<1);
	else
		add(mid+1, R, l, C, rt<<1|1);
	pushup(rt);
}

//区间更新
//update(1,1,2,1,n,1)
//L  R  区间范围
//l 查找的点
//l  r  更新区间
void update(int L,int R,int C, int l, int r, int rt){
	if(L >= l && R <= r){
		ans[rt] = C * (R-L+1);
		lazy[rt] = C;
		return ;
	}
	int mid = (L+R) >> 1;
	pushdown(rt, R-L+1);
	if(r <= mid)	//只在左边更新
		update(L, mid, C, l, r, rt<<1);
	else if(r > mid)	//只在右边更新
		update(mid+1, R, C, l, r, rt<<1|1);
	else{	//两边都要更新
		update(L, mid, C, l, r, rt<<1);
		update(mid+1, R, C ,l, r, rt<<1|1);
	}
	pushup(rt);
}

//查询区间和
//L  R  区间范围
//l  r  查询区间
int query(int L, int R, int l, int r, int rt){
	if(L >= l && R <= r)
	return ans[rt];
	int mid = (L+R)>>1;
	pushdown(rt, R-L+1);
	if(r <= mid)
	return query(L, mid, l, r, rt<<1);
	else if(l > mid)
	return query(mid+1, R, l, r, rt<<1|1);
	else{
		return query(L, mid, l, mid, rt<<1) + query(mid+1, R, mid+1, r, rt<<1|1);
	} 
	//查询区间最值
	//return max(query(L, mid, l, mid, rt<<1),query(mid+1, R, mid+1, r, rt<<1|1));
}
int main()
{
	return;
}

 

 

 

 

相关标签: 线段树