龙空技术网

「算法」线段树

学点干货 296

前言:

此刻朋友们对“算法题树”大体比较关切,朋友们都想要了解一些“算法题树”的相关文章。那么小编在网上搜集了一些对于“算法题树””的相关内容,希望我们能喜欢,小伙伴们快快来学习一下吧!

1、线段树是一棵二叉搜索树,它储存的是一个区间的信息。

2、每个节点以结构体的方式存储,结构体包含以下几个信息:

区间左端点、右端点;(这两者必有)

这个区间要维护的信息(按实际情况而定,数目不等)。

3、线段树的基本思想:二分。

空间大小:

首先是开辟空间,一般设置节点数为N的4倍。证明如下:二叉树是等比数列求和。

公式中a1为首项,an为数列第n项,q为等比数列公比,Sn为前n项和。

x为树的层数,为树的高度+1。二叉树的高度为log2(n)<log2(n)+1,化简可得

整理之后即为4n。

解决问题:

例1:给出n个数,n<=1000000,和m个操作,每个操作可能有两种:1在某个位置加上一个数;2询问区间[l,r]的和,并输出。

例2:给出n个数,n<=1000000,和m个操作,每个操作修改一段连续区间[a,b]的值。

struct node{	int l; //left	int r; //right	int v; //value,这里是求和 int lazy; //懒惰标记}t[maxn*4]; //tree

普通版本的线段树进行的是 单点更新 和 区间查询 。对于带有 懒惰标记 的线段树, 则可以进行 区间更新。懒惰标记记录当前更新值。

void PushUp(int k)//由左孩子、右孩子向上更新父节点{ t[k].v = t[k<<1].v + t[k<<1|1].v;}void build(int k,int l,int r) //建树, k当前节点下标,线段左为l,线段右为r{ t[k].lazy=0; t[k].l=l;t[k].r=r; //线段左端,线段右端 if(l==r) //线段长度为零,结束 { scanf("%d",&t[k].v); return ;  }  int mid=(l+r)>>1; //取线段中点 build(k<<1,l,mid); //k<<1:下标为k节点的左儿子下标,线段左为l,线段右为mid  build(k<<1|1,mid+1,r); //k<<1|1:下标为k节点的右儿子下标,线段左为mid+1,线段右为r PushUp(k); //状态合并,此结点的value为两个孩子的v之和}

向下更新

void PushDown(int k,int num) //向下更新 ,num为子树数量{ if (t[k].lazy) //懒惰标记 { t[k<<1].lazy= t[k<<1|1].lazy = t[k].lazy; t[k<<1].v += (num - (num >> 1)) * t[k].lazy; t[k<<1|1].v += ((num >> 1)) * t[k].lazy; t[k].lazy = 0; }}

更新区间

void Update(int L,int R,int c,int l,int r,int k){ //L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号  if(L <= l && r <= R){ //如果本区间完全在操作区间[L,R]以内  t[k].v +=c*(r-l+1);//更新数字和,向上保持正确  t[k].lazy +=c;//增加标记,表示本区间的v正确,子区间的v仍需要根据lazy标记的值来调整  return ;  }  int m=(l+r)>>1;  PushDown(k,r-l+1); //这里判断左右子树跟[L,R]有无交集,有交集才递归  if(L <= m) Update(L,R,c,l,m,rt<<1);  if(R > m) Update(L,R,c,m+1,r,rt<<1|1);  PushUp(k);//更新本节点信息 } 

区间查询

int Query(int L,int R,int l,int r,int k){//L,R表示操作区间,l,r表示当前节点区间,k表示当前节点编号  if(L <= l && r <= R){  //在区间内,直接返回  return t[k].v;  }  int m=(l+r)>>1;  //下推标记,否则value可能不正确  PushDown(k,r-l+1);  //累计答案  int ANS=0;  if(L <= m) ANS+=Query(L,R,l,m,k<<1);  if(R > m) ANS+=Query(L,R,m+1,r,k<<1|1);  return ANS; } 

标签: #算法题树