我！！！
by Iniaugoty @ 2024-03-02 21:31:23
这题有更新为什么能用分块写?!
by zc_zmb @ 2024-03-03 10:57:41
@[Smiog](/user/399493) dl 能给我看看您的分块是怎么写的吗？我的线段树和分块用时一样。~~但说实话分块比线段树码量小很多~~
这是线段树：
[record](https://www.luogu.com.cn/record/149292462)
code:
```cpp
#include <cstdio>
template <typename T, const int _size> class segment_tree {
protected:
int n;
T tree[_size << 2], flag[_size << 2];
inline void pushup(int pos) {
tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
}
inline void pushdown(int pos, int mid, int l, int r) {
if (flag[pos]) {
tree[pos << 1] += flag[pos] * (mid - l + 1);
tree[pos << 1 | 1] += flag[pos] * (r - mid);
flag[pos << 1] += flag[pos];
flag[pos << 1 | 1] += flag[pos];
flag[pos] = 0;
}
}
void build(T a[], int pos, int l, int r) {
if (l == r) {
tree[pos] = a[l];
return;
}
int mid = l + r >> 1;
build(a, pos << 1, l, mid);
build(a, pos << 1 | 1, mid + 1, r);
pushup(pos);
}
void update(int pos, int l, int r, int left, int right, T v) {
if (l <= left && r >= right) {
tree[pos] += (right - left + 1) * v;
flag[pos] += v;
return;
}
int mid = left + right >> 1;
pushdown(pos, mid, left, right);
if (l <= mid)
update(pos << 1, l, r, left, mid, v);
if (r > mid)
update(pos << 1 | 1, l, r, mid + 1, right, v);
pushup(pos);
}
T query(int pos, int l, int r, int left, int right) {
if (l <= left && r >= right)
return tree[pos];
int mid = left + right >> 1;
pushdown(pos, mid, left, right);
T ans = 0;
if (l <= mid)
ans += query(pos << 1, l, r, left, mid);
if (r > mid)
ans += query(pos << 1 | 1, l, r, mid + 1, right);
return ans;
}
public:
segment_tree() {}
~segment_tree() {}
inline void build(int N, T a[]) {
n = N;
build(a, 1, 1, n);
}
inline void update(int l, int r, T v) {
update(1, l, r, 1, n, v);
}
inline T query(int l, int r) {
return query(1, l, r, 1, n);
}
};
int n, m, opt, x, y;
long long k, a[100005];
segment_tree<long long, 100000> tree;
int main() {
scanf("%d%d", &n, &m);
for (register int i = 1; i <= n; ++i)
scanf("%lld", a + i);
tree.build(n, a);
while (m--) {
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1) {
scanf("%lld", &k);
tree.update(x, y, k);
}
else
printf("%lld\n", tree.query(x, y));
}
return 0;
}
```
这是分块：
[record](https://www.luogu.com.cn/record/149292223)
```cpp
#include <cstdio>
#include <cmath>
template <typename T, const int _size> class block {
protected:
int len, id[_size + 5];
T sum[_size + 5], data[_size + 5], flag[_size + 5];
public:
inline void build(int n, T a[]) {
len = sqrt(n);
for (register int i = 1; i <= n; ++i) {
id[i] = (i - 1) / len + 1;
data[i] = a[i];
sum[id[i]] += data[i];
}
}
inline void modify(int L, int R, T v) {
int l = id[L], r = id[R];
for (register int i = L; id[i] == l && i <= R; ++i) {
data[i] += v;
sum[l] += v;
}
if (l == r)
return;
for (register int i = l + 1; i < r; ++i) {
flag[i] += v;
sum[i] += len * v;
}
for (register int i = R; id[i] == r; --i) {
data[i] += v;
sum[r] += v;
}
}
inline T query(int L, int R) {
int l = id[L], r = id[R];
T ans = 0;
for (register int i = L; id[i] == l && i <= R; ++i)
ans += data[i] + flag[l];
if (l == r)
return ans;
for (register int i = l + 1; i < r; ++i)
ans += sum[i];
for (register int i = R; id[i] == r; --i)
ans += data[i] + flag[r];
return ans;
}
};
int n, m, opt, l, r;
long long v, a[100005];
block<long long, 100000> b;
int main() {
scanf("%d%d", &n, &m);
for (register int i = 1; i <= n; ++i)
scanf("%lld", a + i);
b.build(n, a);
while (m--)
{
scanf("%d%d%d", &opt, &l, &r);
if (opt == 1) {
scanf("%lld", &v);
b.modify(l, r, v);
}
else
printf("%lld\n", b.query(l, r));
}
return 0;
}
```
by 2023gdgz01 @ 2024-03-04 14:07:22
~~本蒟佬第一次写分块~~
by 2023gdgz01 @ 2024-03-04 14:08:32
@[2023gdgz01](/user/891606) 我分块 174ms， 线段树194ms 。
by ShengXuanYi1 @ 2024-03-04 21:35:59