首页 > 其他分享 >线段树—模板

线段树—模板

时间:2024-02-20 17:55:04浏览次数:34  
标签:结点 int 线段 tree lson gjd rson 模板

线段树常见操作

  • build 建树
  • update 更新
  • query 查询
  • pushup 向上回溯
  • pushdown 向下延迟更新(延迟标记)

建线段树:

//预编译命令,做符号代换
#define lson (gjd<<1)
#define rson (gjd<<1|1)

//gjd表示当前结点,[l,r]表示区间范围
void build(int gjd,int l,int r){
    tree[gjd].l=l;
    tree[gjd].r=r;
    if(l==r){
        tree[gjd].max=tree[gjd].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[gjd].sum=tree[lson].sum+tree[rson].sum;
    tree[gjd].max=max(tree[lson].max,tree[rson].max);
}

调用时:build(1,1,n);

更新—单点更新

void update(int gjd,int now,int ans){
	if(tree[gjd].l==tree[gjd].r){//找到对应的叶子结点
		tree[gjd].sum+=ans;//tree[gjd].max=ans;
		return;
	}
	int mid=(tree[gjd].l+tree[gjd].r)>>1;
	if(now<=mid) update(lson,now,ans);
	else update(rson,now,ans);
    //回溯更新父结点信息
	tree[gjd].sum=tree[lson].sum+tree[rson].sum;
	tree[gjd].max=max(tree[gjd].max,tree[rson].max);
}

查询—查询区间和

//当前结点为gjd,要查询的区间为[l,r] 
int query(int gjd,int l,int r){
	//如果结点表示的区间是查询区间的真子集 
	if(l<=tree[gjd].l&&tree[gjd].r<=r)
	   return tree[gjd].sum;
	int mid=(tree[gjd].l+tree[gjd].r)>>1;
	if(r<=mid) return query(lson,l,r);
	else if(l>mid) return query(rson,l,r);
	else return (query(lson,l,r)+query(rson,l,r)); 
}

向上回溯

该函数就是由子结点递归回来,修改父结点中的信息。由于一般建树和更新都有这个相同的操作,因此我们可以写成一个函数,简化代码量

void pushup(int gjd){
    tree[gjd].sum=tree[lson].sum+tree[rson].sum;
    tree[gjd].max=max(tree[lson].max,tree[rson].max);
}

延迟标记

做区间更新时,如果要更新的区间能够完全覆盖当前节点表示的区间,则在此节点上做个标记(表示此节点曾被修改,但子节点尚未被更新),不再继续向下更新,同时在回溯时更新父节点的信息。
 如果在之后的维护或查询过程中需要对这个节点的某个儿子递归地进行处理,则将这个标记分解,传递给它的两个儿子节点。
 这种在需要的时候才进行分解的做法,使我们整体的时间复杂度仍在O(log2N) 的水平上。

//把当前结点gjd的延迟标记下放到左右儿子
void pushdown(int gjd){
	if(tree[gjd].lazy){//此结点有延迟标记 
		int lz=tree[gjd].lazy;
		tree[gjd].lazy=0;//记得清零 
		tree[lson].lazy+=lz;
		tree[rson].lazy+=lz;
		tree[lson].sum+=lz*(tree[lson].r-tree[lson].l+1);
		tree[rson].sum+=lz*(tree[rson].r-tree[rson].l+1);
	}
} 

区间更新

void update(int gjd,int l,int r,int ans){
	//更新区间完全覆盖结点表示的区间
	if(l<=tree[gjd].l&&tree[gjd].r<=r){
		tree[gjd].lazy+=ans;
		tree[gjd].sum+=ans*(tree[gjd].r-tree[gjd].l+1);
		return;
	}
	//如果不能完全覆盖,此时需要向下递归,要下放标记 
	pushdown(gjd);
	int mid=(tree[gjd].l+tree[gjd].r)>>1;
	if(l<=mid) update(lson,l,r,ans);
	if(r>mid) update(rson,l,r,ans);
	pushup(gjd);//更新完回来记得要更新当前结点的信息 
}

区间查询(求和)

int query(int gjd,int l,int r){
	//更新区间完全覆盖结点表示的区间 
	if(l<=tree[gjd].l&&tree[gjd].r<=r)
	   return tree[gjd].sum;
	//如果不能完全覆盖,此时需要向下递归,要下放标记
	pushdown(gjd);
	int mid=(tree[gjd].l+tree[gjd].r)>>1;
	int ans=0;
	if(l<=mid) ans+=query(lson,l,r);
	if(r>mid) ans+=query(rson,l,r);
	return ans; 
}

如有错误,欢迎大佬们在评论区指正~

#一名爱玩狂铁的oier#

标签:结点,int,线段,tree,lson,gjd,rson,模板
From: https://www.cnblogs.com/hzoiwzs/p/18023706

相关文章

  • [COGS 755]山海经:线段树
    这是一道美妙的线段树板子,能够有效地提升我们的读题,理解,思考和代码能力;综上,这是一道大模拟显然,对于这道题的数据范围,直接暴力是行不通的,只能拿30分:30分暴力#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;constintinf=0x7fffffff;structtree{ int......
  • 请求接口生成导入模板
    这里介绍一种通过接口去生成导入数据Excel模板1、controller 2、serviceImpl@OverridepublicvoiddownloadOrderTemplate(HttpServletResponseresponse){List<WorkOrderVoImportDto>orderVoImports=newArrayList<>();try{List......
  • 三哼经(山海经) 线段树
    关于这道题,网上的题解基本都是什么求最大连续子段和,还有什么最大前缀、最大后缀,看了半天也是实在看不明白,便找了个题解,开始给题解写注释(众所周知题解里基本没有注释doge),写了一下午加一晚上,倒是差不多明白了,又肝了0.3坤天终于把三哼经拿下了。题目巴拉巴拉说了一堆没用的的话,让......
  • 线段树-山海经 题解
    《最痛苦的一集》从开始的找维护变量到依据i比较依据y比较最后发现问题出在没初始化(如果不将答案赋值为极小值那么它最小值就是0因此wa了无数遍下面是思路首先要维护的变量有:\(区间的左右边界\,l,\,r\)\(区间的答案\,ans\)\(含左端点最大值\,lans\,和含右端点最......
  • C++ 模板的笔记2
    C++模板的笔记2关于可变参函数模板借鉴了一部分笔记,感谢大佬类模板中的嵌套类模板可以嵌套其他类模板,就像普通类可以嵌套其他普通类一样。嵌套的类模板可以访问外部类模板的成员,包括私有成员。示例:#include<iostream>usingnamespacestd;template<typenameT>classO......
  • 线段树
    线段树算是树状数组的进阶版了,树状数组能做的,线段树也肯定能做,它做不了的,线段树也能做。但确实线段树的代码量也很让人挠头,基本原理不再解释。先看一下基础的模板吧单点修改和区间查询点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=300000;intn......
  • "山海经“ 讲解----线段树
    ”山海经“--线段树讲解1、题面:http://cogs.pro/cogs/problem/problem.php?pid=7752、题目大意及分析:i:大概就是说给了你一段[1,n]的区间,并给了每个区间的权值,下面会有m个问题,每个问题给你一段[1,n]的子区间[i,j],问你在这段区间上的任意一端子区间和最大是多少,并且要求输出这......
  • 线段树的各种板板~(*^▽^*)
    $\color{purple}{板板}$#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineinf0x3f#defineINF0x3f3f3f3f#definemst(a,b)memset(a,b,sizeof(a))#defineElaina0#definelid(id<<1)#definerid(id<<1|1)//即ridco......
  • 线段树模板
    开局宏定义:#include<bits/stdc++.h>#defineintlonglong#definelson(now<<1)//现结点的左孩子#definerson(now<<1|1)//右孩子usingnamespacestd;结构体定义:structNode{intl,r;//表示左右区间intmax,sum;//其他数据域}tree[N<<2]//=N*......
  • 线段树(板子)
    线段树单点修改,单点,区间查询区间修改,单点,区间查询单点修改普通线段树code#definels(rt<<1)#definers(rt<<1|1)#definellllonglongconstintN=1000001;intn,m;inta[N];structT{ intl,r,data;}tr[N<<2];voidpushup(intrt){ tr[rt].da......