当前位置: 首页 > news >正文

分块算法介绍

一 基本概念

分块算法是将所有数据都分成若干块,维护块内信息,而总询问可被看做是若干块儿的询问的总和。

分块算法将长度为 n 的序列分成若干块,每一块都有 k 的元素,最后一块儿可能少于 k 的元素。为了使时间复杂度均摊,通常将块的大小设为 k=sqrt(n),用 pos[i] 表示第 i 个位置所属的块,对每个块儿都进行信息维护。分块可以解决以下问题。

1 单点更新

一般先将对应的块的懒标记下传,再暴力更新块的状态。

2 区间更新

若区间更新横跨若干块,则只需对完全覆盖的块打上标记,最多需要修改两端的两个块,对两端剩余的部分暴力更新块的状态。

3 区间查询

和区间更新类似,对中间跨过的整个块直接利用块存储的信息统计答案,对两端剩余的部分可以暴力扫描统计。

将整个段分成多个块后进行修改或查询时,对完全覆盖的块儿直接进行修改,像线段树一样标记或累加;对两端剩余的部分进行暴力修改,分块算法遵循“大段维护、局部朴素”的原则。

二 算法说明

1 将序列分块,然后将每个块都标记左右端点 L[i] 和 R[i],对最后一块需要特别处理。

n=10,t=sqrt(10)=3,每 3 个元素为一块,一共分成 4 块,最后一块只有一个元素。

2 用 pos[] 标记每个元素所属的块,sum[] 累加每一块的和值。

3 区间更新

将 [i,j] 区间的元素都加上 d。

a 求 l 和 r 所属的块,p=pos[l],q=pos[r]。

b 若属于同一块(p=q),则对该区间的元素进行暴力修改,同时更新该块的和值。

c 若不属于同一块,则对中间完全覆盖的块打上懒标记,add[i]+=d,对首尾两端的元素进行暴力修改。

将 [3,8]区间的元素都加上 5。

4 区间查询

查询 [l,r] 区间的元素和值。

a 求 l 和 r 的所属块,p=pos[l],q=pos[r]。

b 若属于同一块(p=q),则对该区间的元素进行暴力累加,然后加上懒标记上的值。

c 若不属于同一块,则对中间完全覆盖的块累加 sum[] 值和懒标记上的值,然后对首尾两端暴力累加元素值及懒标记值。

查询[2,7]区间的元素和值。

首尾块=5+7+add[1]*(3-2+1)+9+add[3]*(7-7+1)=78

中间块=42+add[2]*(6-2+1)=42+5*3=57

相关文章:

  • 【Git】git的概述、如何下载以及它的工作机制
  • 【springboot进阶】项目构建(二)自定义starter
  • (附源码)计算机毕业设计ssm大学生二手物品交易网站
  • 【计算机网络实验】物理层连接与集线器工作原理实验
  • 如何查看电脑连接过的WiF的密码(Windows版)
  • 在一家虚拟现实公司工作是什么感受?
  • 设计 | 面向对象 - [设计原则总纲与深度理解] TBC...
  • (附源码)计算机毕业设计ssm大学生兼职管理系统
  • C++中的map排序
  • 电子信息类和计算机类专业网课表
  • 赛恩斯环保通过注册:上半年营收2亿 高伟荣家族为实控人
  • 波 特 图
  • 是多重继承
  • 深入分析vhost-user网卡实现原理 —— VirtIO Features协商
  • Pytorch 之torch.nn进阶第1关:正则化
  • 22.<tag-二叉树和树的构建问题>补充: lt.114. 二叉树展开为链表 + lt.108. 将有序数组转换为二叉搜索树 dbc
  • 倡导国稻种芯·中国水稻节 万祥军:稻作文化中国农民丰收节
  • JAVA设计模式-装饰模式
  • MySQL事务的理解
  • Unix五种IO模型