请忽略题目描述。
效率排名
$zkw$ 线段树(159 ms) $>$ 树状数组(170 ms) $>$ 线段树(384 ms) $>$ 分块(1051 ms)
算法1
(分块) $O(n\sqrt{n})$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 320;
typedef long long LL;
int n, m, len;
int w[N];
LL add[M], sum[M];
int find(int i)
{
return i / len;
}
void change(int l, int r, int d)
{
if (find(l) == find(r)) while (l <= r) w[l] += d, sum[find(l ++ )] += d;
else
{
int i = l, j = r;
while (find(i) == find(l)) w[i] += d, sum[find(i ++ )] += d;
while (find(j) == find(r)) w[j] += d, sum[find(j -- )] += d;
for (int k = find(i); k <= find(j); k ++ ) sum[k] += len * d, add[k] += d;
}
}
LL query(int l, int r)
{
LL res = 0;
if (find(l) == find(r)) while(l <= r) res += w[l] + add[find(l ++ )];
else
{
int i = l, j = r;
while (find(i) == find(l)) res += w[i] + add[find(i ++ )];
while (find(j) == find(r)) res += w[j] + add[find(j -- )];
for (int k = find(i); k <= find(j); k ++ ) res += sum[k];
}
return res;
}
int main()
{
scanf("%d %d", &n, &m);
len = sqrt(n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &w[i]);
sum[find(i)] += w[i];
}
int l, r, d;
while (m -- )
{
char op[2];
scanf("%s %d %d", op, &l, &r);
if (op[0] == 'C')
{
scanf("%d", &d);
change(l, r, d);
}
else printf("%lld\n", query(l, r));
}
}
算法2
(线段树) $O(nlogn)$
C++ 代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int l, r, d;
int n, m;
int a[N];
struct Smtree
{
int l, r;
int sum;
int add;
}seg[4 * N];
void pushup(int p)
{
seg[p].sum = seg[p * 2].sum + seg[p * 2 + 1].sum;
}
void pushdown(int p)
{
Smtree &fa = seg[p];
Smtree &left = seg[p * 2], &right = seg[p * 2 + 1];
if (fa.add)
{
left.add += fa.add;
left.sum += (left.r - left.l + 1) * fa.add;
right.add += fa.add;
right.sum += (right.r - right.l + 1) * fa.add;
fa.add = 0;
}
}
void build(int p, int l, int r)
{
seg[p] = {l, r, 0, 0};
if (l == r) {seg[p] = {l, r, a[l], 0}; return;}
int mid = l + r >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
pushup(p);
}
void change(int p, int l, int r, int d)
{
if (seg[p].l >= l && r >= seg[p].r)
{
seg[p].add += d;
seg[p].sum += (seg[p].r - seg[p].l + 1) * d;
return;
}
pushdown(p);
int mid = seg[p].l + seg[p].r >> 1;
if (l <= mid) change(p * 2, l, r, d);
if (r > mid) change(p * 2 + 1, l, r, d);
pushup(p);
}
int query(int p, int l, int r)
{
if (seg[p].l >= l && r >= seg[p].r) return seg[p].sum;
pushdown(p);
int sum = 0;
int mid = seg[p].l + seg[p].r >> 1;
if (l <= mid) sum = query(p * 2, l, r);
if (r > mid) sum += query(p * 2 + 1, l, r);
return sum;
}
signed main()
{
scanf("%lld %lld", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
build(1, 1, n);
while (m -- )
{
char op[2];
scanf("%s", op);
scanf("%lld %lld", &l, &r);
if (op[0] == 'C')
{
scanf("%lld", &d);
change(1, l, r, d);
}
else printf("%lld\n", query(1, l, r));
}
return 0;
}
算法3
(树状数组) $O(nlogn)$
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N];
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i] * i的前缀和
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[], int x, LL c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(LL tr[], int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
int b = a[i] - a[i - 1];
add(tr1, i, b);
add(tr2, i, (LL)b * i);
}
while (m -- )
{
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
else
{
scanf("%d", &d);
// a[l] += d
add(tr1, l, d), add(tr2, l, l * d);
// a[r + 1] -= d
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
}
return 0;
}
算法4
(zkw 线段树) $O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 10;
typedef long long LL;
int n, m, a[M], N;
LL tree[M << 1], mark[M << 1];
void build()
{
N = n - 1;
for (int i = 1; i <= n; i ++ ) tree[i + N] = a[i];
for (int i = N; i; i -- ) tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void change(int l, int r, int d)
{
int len = 1, cntl = 0, cntr = 0;
// (l, r) 开区间
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1)
{
tree[l] += cntl * d, tree[r] += cntr * d;
// l 是左儿子,r 是右儿子
if (!(l & 1)) tree[l ^ 1] += len * d, mark[l ^ 1] += d, cntl += len;
if (r & 1) tree[r ^ 1] += len * d, mark[r ^ 1] += d, cntr += len;
}
for (; l; l >>= 1, r >>= 1) tree[l] += cntl * d, tree[r] += cntr * d;
}
LL query(int l, int r)
{
LL ans = 0, len = 1, cntl = 0, cntr = 0;
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1, len <<= 1)
{
ans += cntl * mark[l] + cntr * mark[r];
if (~l & 1) ans += tree[l ^ 1], cntl += len;
if (r & 1) ans += tree[r ^ 1], cntr += len;
}
for (; l; l >>= 1, r >>= 1)
ans += cntl * mark[l] + cntr * mark[r];
return ans;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
build();
while (m -- )
{
char x[2];
int l, r, d;
scanf("%s %d %d", x, &l, &r);
if (x[0] == 'C')
{
scanf("%d", &d);
change(l, r, d);
}
else printf("%lld\n", query(l, r));
}
}