【算法每日一练]-结构优化（保姆级教程 篇4 树状数组，线段树，分块模板篇）

除了基础的前缀和，后面还有树状数组，线段树，分块的结构优化。

目录

分块

分块算法步骤：

树状数组

树状数组步骤：

线段树点更新

点更新步骤：

线段树区间更新

区间更新步骤：

分块

分块算法多用于求多次区间更新的区间和（在线算法）

题目：（POJ 3648） 一个简单的整数问题

        

分块算法思想：基于优化后的暴力。

分块的本质就是维护每个块的suf数组(和lz)，然后分整个块处理和非整个块暴力处理！

        

分块算法步骤：

        

1，预处理块build：初始化每块的左右下标L[],和R[]，每个下标的所属块号be，每块的和suf

        

2，区间修改update：对于完整的块仅修改懒标lz，不完整的就暴力修改a和suf

        

3，区间查询query ：对于完整的块直接利用懒标lz和suf，不完整的就暴力a和lz

（这里没有什么懒标下放，这又不是求区间max）

#include <bits/stdc++.h>//POJ3648
using namespace std;
const int N=100010;
typedef long long ll;
ll suf[N],lz[N];//分块的本质是维护每个块的suf数组(和lz)，然后分整个块处理和非整个块暴力处理（相当于优化后的暴力）
int a[N],L[N],R[N],be[N];
int n,m;
//分块:我们处理下标都是从1开始
void build(){//L[]R[]每块的左右下标，be[]每个下标的所属块号，suf[]每块的和
	int t=sqrt(n);
	int num=n/t;
	if(n%t) num++;//t是块长，num是块数，
	for(int i=1;i<=num;i++){
		L[i]=(i-1)*t+1;	R[i]=i*t;
	}
	R[num]=n;//更改最后一块的右下标
	for(int i=1;i<=num;i++)
		for(int j=L[i];j<=R[i];j++){
			be[j]=i;suf[i]+=a[j];//初始化每点的be和每块的suf
		}
}
//区间修改
void update (int l,int r,int d){//完整块就修改懒标lz，不完整就修改a，suf
	int p=be[l],q=be[r];
	if(p==q){//如果在同一块就暴力修改a和suf
		for(int i=l;i<=r;i++) a[i]+=d;
		suf[p]+=d*(r-l+1);
	}
	else{//否则：完整的块修改懒标lz，不完整还是暴力a和suf
		for(int i=p+1;i<=q-1;i++) lz[i]+=d;
		for(int i=l;i<=R[p];i++) a[i]+=d;
		suf[p]+=d*(R[p]-l+1);
		for(int i=L[q];i<=r;i++) a[i]+=d;
		suf[q]+=d*(r-L[q]+1);
	}
}

ll query(int l,int r){//完整块suf和lz，不完整就a和lz
	int p=be[l],q=be[r];ll ans=0;
	if(p==q){//同一块就看a和lz
		for(int i=l;i<=r;i++) ans+=a[i];
		ans+=lz[p]*(r-l+1);
	}
	else{//否则：完整就suf+lz，不完整还是a和lz
		for(int i=p+1;i<=q-1;i++) ans+=suf[i]+lz[i]*(R[i]-L[i]+1);
		for(int i=l;i<=R[p];i++) ans+=a[i];
		for(int i=L[q];i<=r;i++) ans+=a[i];
		ans+=lz[q]*(r-L[q]+1);
	}
	return ans;
}

int main(){
	cin>>n>>m;
	int l,r,d;char op[3];//不要输入字符，输入字符串
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build();
	for(int i=1;i<=m;i++){
		scanf("%s %d %d",op,&l,&r);
		if(op[0]=='C'){
			scanf("%d",&d);
			update(l,r,d);
		}
		else{
			printf("%lld\n",query(l,r));
		}
	}
}

        

        

树状数组

树状数组多用于点更新的区间和(在线算法)

树状数组思想：和原数组一一对应，且是通过“二进制 ”分解维护区间

树状数组本质就是创建了一个离散的一维数组c，每个点维护不同区间的前缀和。修改add和查询sum都是离散进行的。性能是log(n)

                
c[i]区间维护长度： i末尾有连续的k个0，则c[i]保存的区间长度为2^k，即从a[i]向前的2^k个元素

         

树状数组步骤：

        
单点修改更新add：找后继  更新该元素所有的祖先节点

                
查询前缀和sum：找前驱    加上左侧所有子树的根（也就是自己的前兄弟，故称为前驱）

        

#include <bits/stdc++.h>//一维树状数组      性能是log(n)
using namespace std;
typedef long long ll;
const int maxn=10000;
ll c[maxn];//c[]为树状数组
int n,a[maxn];
int lowbit(int i){	return (-i)&i;}
//获取c[i]区间的长度(计算机中的负数是以补码来存的)
void add(int i,int z){	for(;i<=n;i+=lowbit(i)) c[i]+=z;}
//c[i]的后继都加上z：直接后继为[i+lowbit(i)]
ll sum(int i){//求前缀和a[1]~a[i]，把i前面所有的根加上即可：直接前驱为[i-lowbit(i)]
	ll s=0;
	for(;i>0;i-=lowbit(i)) s+=c[i];
	return s;
}

ll sum(int i,int j){	return sum(j)-sum(i-1);}//求区间和

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){//数组必须从1开始输入
		cin>>a[i];
		add(i,a[i]);//点更新，更新树状数组
	}	
	int x1,x2;
	cin>>x1;
	cout<<sum(x1)<<'\n';
	cin>>x1>>x2;
	cout<<sum(x1,x2);
	return 0;
}

那么仅仅把sum改成从(1,1)到(x,y)求和即可变成二维的树状数组

#include <bits/stdc++.h>//二维树状数组
using namespace std;
typedef long long ll;
const int maxn=10000;
ll c[maxn][maxn];
int n,a[maxn][maxn];

int lowbit(int i){	return (-i)&i;}

void add(int x,int y,int z){
	for(int i=x;i<=n;i+=lowbit(i))
	for(int j=y;j<=n;j+=lowbit(j)){
		c[i][j]+=z;
	}
}

ll sum(int x,int y){//求(1,1)到(x,y)和
	ll s=0;
	for(int i=x;i>0;i-=lowbit(i))
	for(int j=y;j>0;j-=lowbit(j)){
		s+=c[i][j];
	}
	return s;
}

ll sum(int x1,int y1,int x2,int y2){
	return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		cin>>a[i][j];
		add(i,j,a[i][j]);
	}
	int x1,y1,x2,y2;
	cin>>x1>>y1;
	cout<<sum(x1,y1)<<'\n';
	cin>>x1>>y1>>x2>>y2;
	cout<<sum(x1,y1,x2,y2);
	
}

        

        

线段树点更新

多用于求点更新的区间最值

线段树思想：建立一颗二叉树来用每个节点去维护对应区间的信息

线段树的本质是在4maxn大小的一维dfs序的树形离散数组tree(节点)上存储区间的信息。建立，更新和查询也都是离散的

        

要注意：

我们建立的二叉树在非叶子层时都是满二叉树。所以k节点的左孩子一定是2k，右孩子一定是2k+1另外k(节点)的值和l,r的值没有任何关系，只不过是l==r时候k是叶子节点

        

我们一定是按照dfs序来存储节点的，也因此叶子节点也是dfs序更新的

点更新步骤：

        

build：初始化节点信息：找到叶节点放置数组信息，然后上传到所有节点更新信息

        

update：找到对应的点将i下标的值更新为v

        

query: 找到对正确的节点就返回，否则就继续分叉找

        

千万别看代码多长，基本就函数中最前面的几句有用，剩余操作的都是在找孩子进行递归。

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005,INF=0x3f3f3f3f;
int n,a[maxn];
struct node{  int l,r,mx;}tree[maxn*4];//存放左右端点l,r，mx为区间最值，tree存放树节点号

void build(int k,int l,int r){//创建线段树：初始化每个节点
	tree[k].l=l;tree[k].r=r;
	if(l==r){
		tree[k].mx=a[l];return ;
	}
	int mid=(l+r)/2;
	build(k<<1,l,mid);//建树时候范围一定要变化
	build(k<<1|1,mid+1,r);
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//创建完成孩子后再更新最大值
}

void update(int k,int i,int v){//单点修改：在k节点将i下标的值更新为v
	if(tree[k].l==tree[k].r&&tree[k].l==i){//找i下标的叶子更新
		tree[k].mx=v;return ;
	}
	int mid=(tree[k].l+tree[k].r)/2;
	if(i<=mid) update(k<<1,i,v);//否则就进入左子树lc或右子树更新rc
	else update(k<<1|1,i,v);
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//孩子更新完后修改最大值
}

int query(int k,int l,int r){//区间查询：找到对正确的节点就返回，否则就继续分叉找
	if(tree[k].l>=l&&tree[k].r<=r){
		return tree[k].mx;//找到了
	}
	int mid=(tree[k].l+tree[k].r)/2;
	int maxx=-INF;
	if(l<=mid){//否则就找左子树或右子树的最值
		maxx=max(maxx,query(k<<1,l,r));
	}
	if(r>mid){
		maxx=max(maxx,query(k<<1|1,l,r));
	}
	return maxx;
}

void print(int k){
	if(tree[k].mx){
		cout<<k<<"\t"<<tree[k].l<<"\t"<<tree[k].r<<"\t"<<tree[k].mx<<"\t"<<'\n';
		print(k<<1);
		print((k<<1)+1);
	}
}

int main(){
	int l,r,i,v;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);//创建二叉线段树，为啥传入树根呢？答：方便找左右孩子
	print(1);
	cin>>l>>r;
	cout<<query(1,l,r)<<'\n';//查询区间最值
	cin>>i>>v;
	update(1,i,v);//点更新
	print(1);
	cin>>l>>r;
	cout<<query(1,l,r)<<'\n';
}

输入样例后建立的二叉树： 

        

         

线段树区间更新

 多用于求区间更新的区间最值   

区间更新步骤：

        

创建线段树：初始化节点信息：找到叶节点放置数组信息，然后上传到所有节点更新信息

        

区间修改：在k节点上修改[l,r]区间为v值，整体包含就做懒标，否则就继续分叉（分叉前一定要懒标下移）

        

区间查询：找到对正确的节点就返回，否则就继续分叉找（分叉前一定要懒标下移）

也就是相对点更新来讲多了懒标的处理 

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005,INF=0x3f3f3f3f;
int n,a[maxn];
struct node{  int l,r,mx,lz;}tree[maxn*4];//存放左右端点l,r，mx表示区间[l,r]最值，lz表示懒标 tree存放树节点号
//二叉树的本质是在4k的一维dfs序的树形离散数组(节点)上存储的信息。另外k(节点)的值和l,r的值没有任何关系，只不过是l==r时候k是叶子节点
void lazy(int k,int v){tree[k].mx=tree[k].lz=v;}//给节点k打懒标

void pushdown(int k){//从k节点下传懒标（传给子树），只会传一次，否则就退化成单点修改了
	lazy(k<<1,tree[k].lz);
	lazy(k<<1|1,tree[k].lz);//+的优先级太高了
	tree[k].lz=-1;//清除当前节点懒标
}

void build(int k,int l,int r){//创建线段树：创建二叉树，然后在叶节点放置数组信息，然后上传到所有节点更新信息
	tree[k].l=l;tree[k].r=r;tree[k].lz=-1;//初始化节点
	if(l==r){
		tree[k].mx=a[l];return ;//按dfs顺序更新叶子
	}
	int mid=(l+r)/2;
	build(k<<1,l,mid);//建树时候范围一定要变化
	build(k<<1|1,mid+1,r);//左右孩子节点为2k和2k+1，分别维护[l,mid]和[mid+1,r]的区间信息
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//更新最大值
}

void update(int k,int l,int r,int v){//区间修改：在k节点上修改[l,r]区间为v值，整体包含就做懒标，否则就继续分叉
	if(tree[k].l>=l&&tree[k].r<=r){//恰好找到区间（覆盖也行）
		return lazy(k,v);//直接做懒标记并结束本层，这个return不是返回值的
	}
	if(tree[k].lz!=-1) pushdown(k);//有懒标，先下移再进入子树（这样下个节点的lz和mx就更新了）
	int mid=(tree[k].l+tree[k].r)/2;
	if(l<=mid) update(k<<1,l,r,v);//传节点即可，因为我们用的是节点的信息(build时是l到mid区间为左子树，所以必须l<=mid)
	if(r>mid) update(k<<1|1,l,r,v);
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//更新最大值
}

int query(int k,int l,int r){//区间查询：找到对正确的节点就返回，否则就继续分叉找
	if(tree[k].l>=l&&tree[k].r<=r){//找到就返回
		return tree[k].mx;
	}
	if(tree[k].lz!=-1) pushdown(k);//有懒标，先下移再进入子树
	int mid =(tree[k].l+tree[k].r)/2;
	int maxx=-INF;
	if(l<=mid) maxx=max(maxx,query(k<<1,l,r));//否则就找左子树或右子树的最值
	if(r>mid)  maxx=max(maxx,query(k<<1|1,l,r));
	return maxx;
}

void print(int k){
	if(tree[k].mx){//从根开始dfs顺序访问每个节点（1，2，3 ……）
		cout<<k<<"\t"<<tree[k].l<<"\t"<<tree[k].r<<"\t"<<tree[k].mx<<"\t"<<'\n';
		print(k<<1);
		print(k<<1|1);
	}
}

int  main(){
	int l,r,v;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);//创建线段树 
	print(1);
	cin>>l>>r;
	cout<<query(1,l,r)<<'\n';//区间查询
	cin>>l>>r>>v;
	update(1,l,r,v);//区间修改
	print(1);
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	cout<<"\n";
	while(l){
	cin>>l>>r;
	cout<<query(1,l,r)<<'\n';
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/226241.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【wvp】测试记录

【wvp】测试记录

ffmpeg 这是个莫名其妙的报错&#xff0c;通过排查&#xff0c;应该是zlm哪个进程引起的 会议室的性能 网络IO也就20M
阅读更多...
业绩超预期,股价却暴跌,MongoDB股票还值得投资吗?

业绩超预期,股价却暴跌,MongoDB股票还值得投资吗?

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 尽管MongoDB(MDB)本季度的财报超出了预期&#xff0c;并提高了全年预期&#xff0c;但它的股价在财报发布后还是出现了暴跌。 MongoDB截至2023年10月31日的第三财季&#xff0c;收入同比增长了30%&#xff0c;达到了4.329亿…
阅读更多...
各大电商平台商品详情API调用(API接口)、淘宝API、京东API、拼多多API、1688API文档案例演示

各大电商平台商品详情API调用(API接口)、淘宝API、京东API、拼多多API、1688API文档案例演示

电商API接口的作用主要表现在以下几个方面&#xff1a; 数据支持&#xff1a;通过开放API接口&#xff0c;其他软件、应用、网站等可以访问电商平台的数据库和功能&#xff0c;利用这些数据提供更丰富的功能和更好的服务。例如&#xff0c;API接口可以收集用户的购物记录、搜索…
阅读更多...
第二十一章总结。。

第二十一章总结。。

计算机网络实现了堕胎计算机间的互联&#xff0c;使得它们彼此之间能够进行数据交流。网络应用程序就是再已连接的不同计算机上运行的程序&#xff0c;这些程序借助于网络协议&#xff0c;相互之间可以交换数据&#xff0c;编写网络应用程序前&#xff0c;首先必须明确网络协议…
阅读更多...
状态机的练习：按键控制led灯

状态机的练习：按键控制led灯

设计思路&#xff1a; 三个按键控制led输出。 三个按键经过滤波(消抖)&#xff0c;产生三个按键标志信号。 三个led数据的产生模块&#xff08;流水&#xff0c;跑马&#xff0c;闪烁模块&#xff09;&#xff0c;分别产生led信号。 这六路信号&#xff08;三路按键信号&am…
阅读更多...
4种常见的限流算法

4种常见的限流算法

限流算法 1、固定窗口 含义&#xff1a; 在一个固定长度的时间窗口内限制请求数量&#xff0c;每来一个请求&#xff0c;请求次数加一&#xff0c;如果请求数量超过最大限制&#xff0c;就拒绝该请求 优点&#xff1a; 实现简单&#xff0c;容易理解。 缺点&#xff1a; ①限流…
阅读更多...
Ngxin实现301重定向映射

Ngxin实现301重定向映射

要实现将abc.love域名映射到http://baidu.com网站&#xff0c;并进行重定向&#xff0c;你需要在Nginx的配置文件中添加一个新的server块&#xff0c;如下所示&#xff1a; server {listen 80;server_name abc.com; #替换成自己的域名&#xff0c;记得要映射到这台服务器&…
阅读更多...
element UI改写时间线组件为左右分布

element UI改写时间线组件为左右分布

2023.12.4今天我学习了如何使用element的时间线组件&#xff0c;效果如&#xff1a; 代码如下&#xff1a;&#xff08;关键代码 v-if"item.send_type"&#xff09;判断左右分布情况。因为如果没有这个判断的话&#xff0c;其实会两边都有显示。可以用一个判断表示0显…
阅读更多...
OpenEuler_22.03升级mongdb到7.0.4

OpenEuler_22.03升级mongdb到7.0.4

使用命令&#xff1a;lscpu&#xff0c;查看cpu架构为aarch64为arm架构的一种执行状态。 所以我们直接下载arm的包安装即可。无需自己编译源码。 下载地址&#xff1a;https://www.mongodb.com/try/download/community 下载解压 wget https://fastdl.mongodb.org/linux/mong…
阅读更多...
使用腾讯逆地理位置编码获取地理位置信息

使用腾讯逆地理位置编码获取地理位置信息

文章目录 前言一、代码二、开放平台操作步骤1.开发者认证2.创建应用 总结 前言 最近项目中一个发帖的功能需要获取当前用户的发帖位置&#xff0c;由于是在APP内部使用&#xff0c;而且APP是使用uniApp开发的&#xff0c;所以在使用开放平台的SDK选用上有些麻烦&#xff0c;有…
阅读更多...
echarts环形饼图

echarts环形饼图

效果示例 代码汇总 pieCharts() {let data [];const providerResult [{name: 智诺, value: 23},{name: 海康, value: 5},{name: 大华, value: 5}, {name: 云科, value: 23},{name: 四信, value: 22},{name: 九物, value: 22}]let charts echarts.init(document.getElemen…
阅读更多...
11K+ Star！图解计算机网络、操作系统、计算机组成、数据库！

11K+ Star！图解计算机网络、操作系统、计算机组成、数据库！

大家好&#xff0c;我是 Java陈序员。 俗话说得好&#xff0c;面试造火箭&#xff0c;入职拧螺丝。我们在工作中&#xff0c;其实很少用到一些计算机底层知识&#xff0c;往往只要编码完事。但是&#xff0c;知其然还要知其所以然&#xff0c;我们不仅要做一个合格的“CV 工程…
阅读更多...
Vector Quantized Diffusion Model for Text-to-Image Synthesis

Vector Quantized Diffusion Model for Text-to-Image Synthesis

Vector Quantized Diffusion Model for Text-to-Image Synthesis Shuyang Gu, University of Science and Technology of China, Microsoft, CVPR2022, Cited: 340, Code, Paper 1. 前言 我们提出了用于文本到图像生成的矢量量化扩散(Vector Quantized Diffusion Model&…
阅读更多...
JavaScript如何实现按键音效、视频播放，标签分类切换横向滚动

JavaScript如何实现按键音效、视频播放，标签分类切换横向滚动

1.使用HTML5的audio标签 &#xff08;音频播放&#xff09; <audio id"click-sound"><source src"audio/show.mp3" type"audio/mpeg"> </audio> <button id"button">按钮</button> var clickSound d…
阅读更多...
北京市经信局局长姜广智带队调研三六零 强调大模型应与行业结合

北京市经信局局长姜广智带队调研三六零 强调大模型应与行业结合

12月6日&#xff0c;北京市经济和信息化局局长姜广智、副局长王磊带队走访调研三六零集团&#xff0c;就共促城市级数字安全基础设施项目落地&#xff0c;打造引领行业发展标杆项目&#xff0c;推动大模型落地应用赋能产业、行业发展等话题进行交流。360集团创始人周鸿祎接待来…
阅读更多...
【FPGA】Quartus18.1打包封装网表文件（.qxp）详细教程

【FPGA】Quartus18.1打包封装网表文件（.qxp）详细教程

当我们在做项目的过程中&#xff0c;编写的底层Verilog代码不想交给甲方时怎么办呢&#xff1f;此时可以将源代码打包封装成网表文件&#xff08;.qxp&#xff09;进行加密&#xff0c;并且在工程中进行调用。 Quartus II的.qxp文件为QuartusII Exported Partition&#xff0c;…
阅读更多...
探索 Linux Namespace：Docker 隔离的神奇背后

探索 Linux Namespace：Docker 隔离的神奇背后

来自&#xff1a;探索云原生 https://www.lixueduan.com 原文&#xff1a;https://www.lixueduan.com/posts/docker/03-container-core/ 在 深入理解 Docker 核心原理&#xff1a;Namespace、Cgroups 和 Rootfs 一文中我们分析了 Docker 是由三大核心技术实现的。 今天就一起分…
阅读更多...
C++多态（详解）

C++多态（详解）

一、多态的概念 1.1、多态的概念 多态&#xff1a;多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。 举个例子&#xff1a;比如买票这个行为&#xff0c;当普通人买票时&#xff0c;是全价买票&#xff1b;学生买票时&am…
阅读更多...
【离散数学】——期末刷题题库（等价关系与划分）

【离散数学】——期末刷题题库（等价关系与划分）

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…
阅读更多...
漏洞复现-速达软件全系产品存在任意文件上传漏洞（附漏洞检测脚本）

漏洞复现-速达软件全系产品存在任意文件上传漏洞（附漏洞检测脚本）

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…
阅读更多...
最新文章

Copyright @ 2022~2023