分块——最为优雅的暴力

在信息学竞赛中,常常会遇到一些区间修改或区间查询的题目,如果直接敲暴力的话,时间复杂度是 O ( n m ) O(nm) O(nm) 可能会超时,如果写树状数组或线段树的话,又有一点复杂,不易理解,那么这时候就要请出我们今天的主角——分块

分块简述

分块分块,顾名思义,就是把一个区间分成几小块,然后对于每个块进行单独的处理。它的核心思想是 将一个大规模的输入划分成更小的“块”,然后针对每一块单独处理。这种方法可以显著降低时间复杂度和空间复杂度,尤其适合 处理静态数据的查询问题。例如,区间求和、最值查询等。

分块的优缺点

分块的优点在于:

  1. 局部化处理:只需要处理相关的块,而无需遍历整个数据集。
  2. 灵活性:通过调整块大小,可以在时间复杂度和空间复杂度之间找到平衡。
  3. 降低查询和更新的复杂度:通常可以将复杂度降低到 O ( n ) O(\sqrt{n}) O(n ) O ( log ⁡ n ) O(\log n) O(logn)级别。

分块的缺点在于:

  1. 容易被卡时间:当我们遇到要进行添加元素的题目的时候,就会被卡时间复杂度,如果出题人非常的毒瘤,他可能会往一个块里使劲加,从而是这个块非常的大(但是有办法解决)
  2. 时间复杂度不够低:因为线段树是 O ( n log ⁡ n ) O(n \log n) O(nlogn) 级的时间复杂度,所以有些题目可能不支持 O ( n n ) O(n \sqrt n) O(nn ) 算法通过,这就非常的尴尬。

分块算法的具体实现步骤

下面我们通过一个简单的例子来展示分块的实现过程:假设我们有一个数组,需要多次进行区间求和查询。

1. 确定块的大小

假设数组有 n n n 个元素。通常,为了优化时间复杂度,我们把块大小设为 B = n B = \sqrt{n} B=n ,这样会得到 n B ≈ n \frac{n}{B} \approx \sqrt{n} Bnn 个块。(证明见1

  • 如果块的大小太小,块的数量会很多,可能导致整体复杂度增加。
  • 如果块的大小太大,单个块的查询效率会下降。

示范代码

k=sqrt(n);
2. 构建块
  • 将数组划分成多个块,例如第一个块是数组的前 (B) 个元素,第二个块是接下来的 (B) 个元素,依此类推。
  • 对每一个块进行预处理,存储它们的总和其他需要的信息。这样,在进行查询时,我们可以直接访问块的预处理结果。

举个例子,假设我们有一个数组 arr:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],我们把它分成 3 个块,每块大小为 3。

示范代码

for (int i=1;i<=n;i++){cin>>a[i];pos[i]=(i-1)/k+1;//存储当前元素应该在第几号块
}
3. 预处理块

对每个块计算并保存其总和。例如,以上数组分块后的块求和是:

  • 块1(包含1, 2, 3):总和为 6
  • 块2(包含4, 5, 6):总和为 15
  • 块3(包含7, 8, 9):总和为 24

这些块的总和我们存储在一个新数组 block_sum 中,方便后续快速访问。

for (int i=1;i<=n;i++){block_sum[pos[i]]+=a[i];
}
4. 实现查询操作

假设我们要查询某个区间内元素的和,例如查询 arr[2]arr[8] 的和,我们可以按照以下步骤进行:

  1. 先处理起始和结束块内部的部分(因为区间可能不是完整的块)。
  2. 直接使用块的预处理结果,跳过中间完整的块。对于中间完整的块,可以直接使用 block_sum 中的值,不用遍历。

例如,查询 arr[2]arr[8],我们可以分三部分处理:

  • 第一个块处理 arr[2]arr[2],即3。
  • 中间的完整块(块2)总和直接用 block_sum 中的值:15。
  • 最后一个块处理 arr[6]arr[8],即 7 + 8 + 9 = 24

这样,总和就是 3 + 15 + 24 = 42,我们没有遍历所有元素,而是用了预处理好的块和结果。

void update1(){int ans=0;for (int i=l;i<=min(r,pos[l]*k);i++){//处理两侧的零散空间ans+=a[i];}if (pos[l]==pos[r])return;for (int i=(pos[r]-1)*k+1;i<=r;i++){ans+=a[i];}for (int i=pos[l]+1;i<=pos[r]-1;i++){ans+=block_sum[i];}cout<<ans<<endl;return;
}
5. 更新操作(可选)

如果需要动态更新数据,例如改变数组中的某个值,我们也可以通过分块来处理。

  • 更新某个元素时,我们更新所在块的总和即可,而不需要重新计算所有块。
  • 例如将 arr[3] 改成10,那么对应块1的和就要相应调整。
void update1(){for (int i=l;i<=min(r,pos[l]*k);i++){a[i]+=c;}if (pos[l]==pos[r])return;for (int i=(pos[r]-1)*k+1;i<=r;i++){a[i]+=c;}for (int i=pos[l]+1;i<=pos[r]-1;i++){plu[i]+=c;plu[i]%=MOD;}return;
}

分块算法的时间复杂度分析

  • 查询复杂度:由于分块后的查询只需要遍历开头和结尾的部分块,再加上中间的少数块总和,时间复杂度通常是 O ( n ) O(\sqrt{n}) O(n )
  • 更新复杂度:每次更新时只需要修改一个块的总和,复杂度也是 O ( n ) O(\sqrt{n}) O(n )

小结

分块算法通过 划分数据、预处理块信息、优化查询效率 等手段,适用于大数据量下的区间查询类问题。
这种思想也延展到了 莫队算法线段树 等高级数据结构中,为复杂查询问题提供了高效解决方案。

上例题(基础的我们就不看了,上点有强度的)

例题

例1

在这里插入图片描述
打眼一瞧,懵了,啥玩意这是?和我们刚刚讲的是一个玩意吗?
不慌,我们慢慢来分析。
首先操作一我们是会的吧,上面有模板,接下来就看操作二。
如果我们每次都是去暴力枚举的话,时间复杂度直接到达 O ( n m ) O(nm) O(nm) ,承受不住。那怎么办?用二分,如果我对每个块都排一遍序的话,是不是就可以用二分来找到 c 2 c^2 c2 的位置了?这是有人就会问了,尽管我们在对整个块进行操作的时候,不会有错,但是在对两侧零散的块进行操作的时候呢?这不简单?直接将左右两侧零散的块给重新排个序不就行了?
这样的时间复杂度就是 O ( n n log ⁡ n ) O(n \sqrt{n} \log {\sqrt n}) O(nn logn )

#include<bits/stdc++.h>
using namespace std;
const int INF=50000+10;
int a[INF],cla[INF],tot[INF];
int k,n;
vector<int> t[250];void resort(int x){t[x].clear();for (int j=(x-1)*k+1;j<=min(n,x*k);j++){t[x].push_back(a[j]);}sort(t[x].begin(),t[x].end());return;
}
void imp(int l,int r,int c){ for (int i=l;i<=min(r,cla[l]*k);i++){a[i]+=c;}resort(cla[l]);if (cla[l]==cla[r])return;for (int i=r;i>=(cla[r]-1)*k+1;i--){a[i]+=c;}resort(cla[r]);for (int i=cla[l]+1;i<cla[r];i++){tot[i]+=c;}return;
}void pro(int l,int r,int c){int ans=0;for (int i=l;i<=min(r,cla[l]*k);i++){if (a[i]+tot[cla[l]]<c*c)ans++;}if (cla[l]==cla[r]){cout<<ans<<endl;return;}for (int i=r;i>=(cla[r]-1)*k+1;i--){if (a[i]+tot[cla[r]]<c*c)ans++;}for (int i=cla[l]+1;i<cla[r];i++){int place=lower_bound(t[i].begin(),t[i].end(),c*c-tot[i])-t[i].begin();ans+=place;}cout<<ans<<endl;return;
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;k=sqrt(n);for (int i=1;i<=n;i++){cin>>a[i];cla[i]=(i-1)/k+1;t[cla[i]].push_back(a[i]);}for (int i=1;i<=cla[n];i++){sort(t[i].begin(),t[i].end());}for (int i=1;i<=n;i++){int opt,l,r,c;cin>>opt>>l>>r>>c;if (opt==0){imp(l,r,c);}else {pro(l,r,c);}}return 0;
}

  1. 设每个块的大小为 B B B 个元素,那么我们总共有 n B \frac{n}{B} Bn 个块如果查询一个随机区间 [ L , R ] [L,R] [L,R],则需要遍历 起始和结束的两个部分块,并直接使用 中间完整块 的预处理结果。由此可见此,查询的时间复杂度可以近似分解为以下两部分:遍历两个不完整块中的元素,复杂度为 O ( B ) O(B) O(B) 查询中间完整块,复杂度为 O ( n B ) O(\frac{n}{B}) O(Bn)
    所以,查询的总时间复杂度为: O ( B ) + O ( n B ) O(B)+O(\frac{n}{B}) O(B)+O(Bn)
    为了找到最优的块大小 B B B ,我们可以将 O ( B ) + O ( n B ) O(B)+O(\frac{n}{B}) O(B)+O(Bn) 视为一个函数,并对其求导来最小化它,
    T ( B ) = B + n B T(B)=B+\frac{n}{B} T(B)=B+Bn ,对 T ( B ) T(B) T(B) 关于 B B B 求导得 T ′ ( B ) T^′(B) T(B) 并设为0。
    则有 T ′ ( B ) = 1 − n B 2 = 0 T^′ (B)=1−\frac{n}{B^2}=0 T(B)=1B2n=0
    解这个方程的 B = n B=\sqrt n B=n ↩︎

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

w~视觉~合集20~SAM

我自己的原文哦~ https://blog.51cto.com/whaosoft/12500982 #SAM 今天&#xff0c;Meta发布史上首个图像分割基础模型SAM&#xff0c;将NLP领域的prompt范式引进CV&#xff0c;让模型可以通过prompt一键抠图。网友直呼&#xff1a;CV不存在了! 就在刚刚&#xff0c;Meta AI…

Halcon resistor.hedv 使用多个对焦级别提取深度

depth_from_focus * Extract depth using multiple focus levels * 使用多个对焦级别提取深度 Names : [] * 初始化一个空数组&#xff0c;用于存储图像名称 dev_close_window () * 关闭当前打开的图像窗口 for i : 1 to 10 by 1 * 循环开始&#xff0c;从1到10 …

qt QTreeWidgetItem详解

1、概述 QTreeWidgetItem 是 Qt 框架中的一个类&#xff0c;专门用于在 QTreeWidget&#xff08;一个基于项的树形视图&#xff09;中表示单个节点&#xff08;或称为项&#xff09;。QTreeWidget 继承自 QAbstractItemView&#xff0c;而 QTreeWidgetItem 则作为树中的一个节…

三.Linux用户和用户管理

前言&#xff1a;Linux系统是一个多用户多任务的分时操作系统&#xff0c;任何一个要使用资源的都必须向系统管理员申请一个账户&#xff0c;然后通过这个账户的身份进入系统。 一.此次目的 用户账号的添加、删除与修改。 用户口令的管理。 用户组的管理。 二.用户账号的添加…

SpringBoot技术栈:构建高效共享汽车系统

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…

【笔记】扩散模型(九):Imagen 理论与实现

论文链接&#xff1a;Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding 非官方实现&#xff1a;lucidrains/imagen-pytorch Imagen 是 Google Research 的文生图工作&#xff0c;这个工作并没有沿用 Stable Diffusion 的架构&#xff0c;而是级…

css:基础

前言 我们之前其实也可以写出一个看起来算是一个网页的网页&#xff0c;为什么我们还要学css&#xff1f; CSS&#xff08;Cascading Style Sheets&#xff09;也叫层叠样式表&#xff0c;是负责美化的&#xff0c;我们之前说html就是一个骨架&#xff0c;css就可以用来美化网…

[全网最细数据结构完整版]第七篇:3分钟带你吃透队列

目录 1->队列的概念及结构 2->队列的实现 2.1定义队列基本结构 struct QueueNode 和 struct Queue 2.2队列初始化函数 QueueInit 函数 2.3队列销毁函数 QueueDestroy 函数 2.4队列插入数据函数 QueuePush 函数 2.5判断队列是否为空,空返回true,非空返回false 2.6队列删…

Android笔记(三十五):用责任链模式封装一个App首页Dialog管理工具

背景 项目需要在首页弹一系列弹窗&#xff0c;每个弹窗是否弹出都有自己的策略&#xff0c;以及哪个优先弹出&#xff0c;哪个在上一个关闭后再弹出&#xff0c;为了更好管理&#xff0c;于是封装了一个Dialog管理工具 效果 整体采用责任链模块设计&#xff0c;控制优先级及弹…

掌握软件组件/单元测试中的这些术语,你就算正式入门了

上篇干货&#xff0c;和大家分享了软件测试的几个级别&#xff0c;在【组件/单元测试】当中&#xff0c;涉及不少名词术语。从之前的学员学习过程来看&#xff0c;这里比较容易出现概念混乱&#xff0c;进而导致面试过程中频频翻车&#xff0c;所以有必要在这里单独拎出来和大家…

html的week控件 获取周(星期)的第一天(周一)和最后一天(周日)

html的week控件 获取周(星期)的第一天(周一)和最后一天(周日) <input type"week" id"week" class"my-css" value"ViewBag.DefaultWeek" /><script> function PageList() { var dateStrin…

【主机游戏】艾尔登法环游戏攻略

艾尔登法环&#xff0c;作为一款备受好评但优化问题频发的游戏&#xff0c;就连马斯克都夸过 今天介绍一下这款游戏 https://pan.quark.cn/s/24760186ac0b 角色升级 在《艾尔登法环》中&#xff0c;角色升级需要找到梅琳娜。你可以在关卡前废墟的营地附近&#xff0c;风暴关…

CSS 中三角形的绘制方法详解

在网页设计领域&#xff0c;特殊形状常常能为页面增添独特的视觉效果&#xff0c;三角形便是其中之一。本文将详细介绍如何利用 CSS 绘制三角形。 一、原理阐述 CSS 中一个元素的边框分为上边框、右边框、下边框和左边框。当把一个元素的宽度和高度设为 0&#xff0c;且只让其…

虚拟机linux7.9下安装mysql

1.MySQL官网下载安装包&#xff1a; MySQL :: Download MySQL Community Server https://cdn.mysql.com/archives/mysql-5.7/mysql-5.7.39-linux-glibc2.12-x86_64.tar.gz 2.解压文件&#xff1a; #tar xvzf mysql-5.7.39-linux-glibc2.12-x86_64.tar.gz 3.移动文件&#…

负载均衡式在线oj项目开发文档(个人项目)

项目目标 需要使用的技术栈&#xff1a; 这个项目共分成三个模块第一个模块为公共的模块&#xff0c;用于解决字符串处理&#xff0c;文件操作&#xff0c;网络连接等等的问题。 第二个模块是一个编译运行的模块&#xff0c;这个模块的主要功能就是将用户的代码收集上来之后要…

MySQL数据库专栏(五)连接MySQL数据库C API篇

摘要 本篇文章主要介绍通过C语言API接口链接MySQL数据库&#xff0c;各接口功能及使用方式&#xff0c;辅助类的封装及调用实例&#xff0c;可以直接移植到项目里面使用。 目录 1、环境配置 1.1、添加头文件 1.2、添加库目录 2、接口介绍 2.1、MySql初始化及数据清理 2.1.…

PH热榜 | 2024-11-08

DevNow 是一个精简的开源技术博客项目模版&#xff0c;支持 Vercel 一键部署&#xff0c;支持评论、搜索等功能&#xff0c;欢迎大家体验。 在线预览 1. Quorini 标语&#xff1a;几分钟内设计并运行无服务器云 API 介绍&#xff1a;Quorini 提供了一套可视化的工具&#xff…

QML:Menu详细使用方法

目录 一.性质 二.作用 三.方法 四.使用 1.改变标签 2.打开本地文件 3.退出程序 4.打开Dialog 五.效果 六.代码 在 QML 中&#xff0c;Menu 是一个用于创建下拉菜单或上下文菜单的控件。它通常由多个 MenuItem 组成&#xff0c;每个 MenuItem 可以包含文本、图标和快捷…

k8s 处理namespace删除一直处于Terminating —— 筑梦之路

问题现象 k8s集群要清理某个名空间&#xff0c;把该名空间下的资源全部删除后&#xff0c;删除名空间&#xff0c;一直处于Terminating状态&#xff0c;无法完全清理掉。 如何处理 为什么要记录下这个处理的步骤&#xff0c;经过查询资料&#xff0c;网上也有各种各样的方法&…

>>,<<,~,,|,∧

‌监视器中的数值在十六进制显示时没有负数&#xff0c;主要是因为十六进制本身不直接表示负数&#xff0c;而是通过补码的形式来表示。