分块算法的公式和程序代码
时间: 2024-05-19 15:14:11 浏览: 143
分块算法的公式:
1. 将数据分为若干块,每块包含固定数量的元素;
2. 预处理每个块的信息,例如:最大值、最小值、平均值等;
3. 对于查询操作,确定查询区间的块范围,然后暴力计算这些块中的元素;
4. 对于修改操作,找到包含该元素的块,更新该块的信息。
分块算法的程序代码:
下面是一个使用分块算法求解区间最大值的示例程序(C++实现):
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100005;
const int MAXB = 320;
int n, m, a[MAXN], block[MAXB], maxv[MAXB];
int block_id(int x) { return (x - 1) / sqrt(n); }
void build() {
int b = sqrt(n);
for (int i = 0; i < n; i++) {
block[i / b] += a[i];
maxv[i / b] = max(maxv[i / b], a[i]);
}
}
void update(int x, int v) {
int b = sqrt(n);
block[x / b] += v - a[x];
maxv[x / b] = max(maxv[x / b], v);
a[x] = v;
}
int query(int l, int r) {
int b = sqrt(n);
int lb = block_id(l), rb = block_id(r);
if (lb == rb) {
int res = 0;
for (int i = l; i <= r; i++) res = max(res, a[i]);
return res;
}
int res = maxv[lb], i;
for (i = l; block_id(i) == lb; i++) res = max(res, a[i]);
for (i = r; block_id(i) == rb; i--) res = max(res, a[i]);
for (int j = lb + 1; j < rb; j++) res = max(res, maxv[j]);
return res;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
build();
for (int i = 0; i < m; i++) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) update(x - 1, y);
else cout << query(x - 1, y - 1) << endl;
}
return 0;
}