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

分块莫队学习笔记

news 2026/5/12 18:38:54

前言

注：本文章未完工

分块和莫队都是暴力，与dfsbfs的区别就是分块和莫队更优雅（bushi），分块和莫队的复杂度是更优的，甚至有的时候复杂度是优于某些数据结构的，类似线段树

分块

让我们来优雅的打暴力吧

分块其实是一种思想，基本思想就是将一个数组，划分成规定长度的块，并在每个块进行预处理等操作，这样的操作明显是优于暴力的 $O(n^2)$，分块的复杂度为 $O(\sqrt{n})$ ，可见时间复杂度十分优秀。

分块的时间复杂度是取决于块长的，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。分块十分灵活，相较线段树，树状数组等数据结构，分块的优点是是通用性更好，甚至可以维护一些线段树做不到的骚操作

分块的缺点是渐近意义的复杂度，相较于线段树和树状数组不够好，但在大部分题都是最优的

T348695 一个简单的整数问题2

本题用到的思想就是分块，设块长为l，记录每个块的和为b，原数组为a，则可列以下式子：

$\underbrace{a_1,a_2,a_3,...,a_l}_{b_1},\underbrace{a_{l+1},a_{l+2},...,a_{2l}}_{b_2},\underbrace{a_{2l+1},a_{2l+2},...,a_{3l}}_{b_3},\underbrace{...}_{b_{...}},\underbrace{a_{(l-1)*l+1},...,a_n}_{b_{\frac n l}}$

那么我们就可以写出一个init初始化函数：
sum就是每个块的和，$pos_i$ 表示i这个位置属于哪个块，L和R表示块的左右区间边界

void init(){int cnt = sqrt(n);for(int i = 1 ; i <= cnt ; i ++){L[i] = (i - 1) * cnt + 1;R[i] = i * cnt;  } if(R[cnt] < n){cnt ++;L[cnt] = R[cnt - 1] + 1;R[cnt] = n; } for(int i = 1 ; i <= cnt ; i ++){for(int j = L[i] ; j <= R[i] ; j ++){pos[j] = i;sum[i] += a[j];} } }

区间的修改以及查询的思路就很好想了

区间修改

拿到一个l,r，首先需要获取l和r都属于哪个块，如果l和r在一个块内，则暴力处理即可，不在一个块内就先把l在块，和r所在块之间的块通过打标记来完成修改操作，再分别暴力处理l所在块与r所在块

void modify(int l, int r, int c){int p = pos[l], q = pos[r];if(p == q){for(int i = l ; i <= r ; i ++){a[i] += c;}sum[p] += (r - l + 1) * c;return ;}for(int i = p + 1 ; i < q ; i ++){lz[i] += c;}for(int i = l ; i <= R[p] ; i ++){a[i] += c;}sum[p] += (R[p] - l + 1) * c;for(int i = L[q] ; i <= r ; i ++){a[i] += c;}sum[q] += (r - L[q] + 1) * c;}

区间查询

大体和区间修改思路一样，处理区间和的时候记得把懒标记加上

int query(int l, int r){int ans = 0;int p = pos[l], q = pos[r];if(p == q){for(int i = l ; i <= r ; i ++){ans += a[i];}ans += (r - l + 1) * lz[p];return ans;}for(int i = p + 1 ; i < q ; i ++){ans += sum[i] + (R[i] - L[i] + 1) * lz[i];}for(int i = l ; i <= R[p] ; i ++){ans += a[i];}ans += (R[p] - l + 1) * lz[p];for(int i = L[q] ; i <= r ; i ++){ans += a[i];}ans += (r - L[q] + 1) * lz[q];return ans;}

综合一下即可

【参考代码】

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 1e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;int n, m;
int a[N]; 
int L[N], R[N];
int pos[N], sum[N];
int lz[N]; void init(){int cnt = sqrt(n);for(int i = 1 ; i <= cnt ; i ++){L[i] = (i - 1) * cnt + 1;R[i] = i * cnt;  } if(R[cnt] < n){cnt ++;L[cnt] = R[cnt - 1] + 1;R[cnt] = n; } for(int i = 1 ; i <= cnt ; i ++){for(int j = L[i] ; j <= R[i] ; j ++){pos[j] = i;sum[i] += a[j];} } }void modify(int l, int r, int c){int p = pos[l], q = pos[r];if(p == q){for(int i = l ; i <= r ; i ++){a[i] += c;}sum[p] += (r - l + 1) * c;return ;}for(int i = p + 1 ; i < q ; i ++){lz[i] += c;}for(int i = l ; i <= R[p] ; i ++){a[i] += c;}sum[p] += (R[p] - l + 1) * c;for(int i = L[q] ; i <= r ; i ++){a[i] += c;}sum[q] += (r - L[q] + 1) * c;}int query(int l, int r){int ans = 0;int p = pos[l], q = pos[r];if(p == q){for(int i = l ; i <= r ; i ++){ans += a[i];}ans += (r - l + 1) * lz[p];return ans;}for(int i = p + 1 ; i < q ; i ++){ans += sum[i] + (R[i] - L[i] + 1) * lz[i];}for(int i = l ; i <= R[p] ; i ++){ans += a[i];}ans += (R[p] - l + 1) * lz[p];for(int i = L[q] ; i <= r ; i ++){ans += a[i];}ans += (r - L[q] + 1) * lz[q];return ans;}signed main(){cin>>n>>m;for(int i = 1 ; i <= n ; i ++){cin>>a[i];}init();while(m --){char op;int l, r, x;cin>>op>>l>>r;if(op == 'C'){cin>>x;modify(l, r, x);}else if(op == 'Q'){cout<<query(l, r)<<'\n';}}return 0;
}