ACM入门之【分块】
入门 ACM 分块
2023-09-11 14:15:52 时间
分块是一种思想,而不是一种数据结构。
分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。
分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某个问题下的最优块长,以及相应的时间复杂度。
分块是一种很灵活的思想,相较于树状数组和线段树,分块的优点是通用性更好,可以维护很多树状数组和线段树无法维护的信息。
当然,分块的缺点是渐进意义的复杂度,相较于线段树和树状数组不够好。
不过在大多数问题上,分块仍然是解决这些问题的一个不错选择。
一般取块的长度为 len=sqrt(n)
, 此时单次操作的时间复杂度最优,时间复杂度为:O(
n
\sqrt{n}
n )
分块算法大致分为如下几步:
- 求分块后,一个块的大小。
- 对每个数都标记其对应所属的块。
- 在执行操作的时候,对于不完整的块暴力处理,完整的块进行处理的标记。
分块标记每个编号所属的块的模板:
len = sqrt(n);
for (int i = 1; i <= n; i++) id[i]=(i-1)/len+1;
区间修改,单点查询模板:
const int N = 1e5 + 10;
typedef long long int LL;
LL a[N], ad[N], id[N], n, m, len;
//ad[i] 编号为i的块加的总数 id[i] i所对应的块
void add(int l, int r, int v) //[l,r]内加v
{
for (int i = l; i <= min(r * 1ll, id[l]*len); i++) a[i] += v; //开头的不完整的
if (id[l] == id[r]) return;//在一个块里
for (int i = id[l] + 1; i <= id[r] - 1; i++) ad[i] += v;//中间完整的块
for (int i = (id[r] - 1) * len + 1; i <= r; i++) a[i] += v;//结束不完整的
}
LL query(int x) //查询x的位置的值
{
return a[x] + ad[id[x]];
}
相关文章
- JavaWeb_(Mybatis框架)MyBatis Generator简单入门
- Yii 框架学习--01 框架入门
- Unity3D热更新LuaFramework入门实战
- 机器学习入门17 - 嵌套 (Embedding)
- Freemarker 页面静态化技术使用入门案例
- Atitit it领域知识点 划分 acm18知识树 目录 1. Acm总结的18个计算机科学关键领域 ACM知识树1 1.1. 大学级别的计算机科学知识可以归纳成14个知识领域:3 2. U
- Java中的URL类&根据url获取网络文件&快速入门Java中的URL(网络编程)
- Spark入门,概述,部署,以及学习(Spark是一种快速、通用、可扩展的大数据分析引擎)
- AngularJS入门心得1——directive和controller如何通信
- y141.第八章 Servless和Knative从入门到精通 -- Serving及实践、Revision和流量管理(五)
- Linux下一个C(编程入门.h档,.c档,而路多文件的调用)
- SIP入门(二):建立SIPserver
- Ubuntu菜鸟入门(四)—— 搜狗输入法
- Kotlin入门简介
- nebula入门学习——day1 nebula基本概念、原理和架构
- TensorFlow 从入门到精通(-1)—— 源代码
- 目标检测入门