POJ-3468 A Simple Problem with Integers 分块 线段树区间更新

POJ-3468 A Simple Problem with Integers

题意： 给定一个数字序列， 有两张操作： 1. 查询[L, R] 的所有数字之和。2. 给定区间[L, R] 的所有数加C.
分析： 很明显的线段树区间更新问题， 但是在这里要引入一种新的算法------分块。 分块的思想就是把区间分为相等的块， 大小一般为sqrt（n）, 在进行操作的时候直接对块进行操作， 查询和更新的时间复杂度可以达到sqrt（n）， 与线段树的时间复杂度不相上下。 这道题是一道很经典的分块和线段树区间更新问题， 下面的代码可以当做模板，下面给出两种代码， 即线段树和分块。要注意的是， 在分块的时候也要使用lazy标记， 表示在分块区间的累加值， 在查询的时候直接加入到结果中即可。
分块代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int MAXN = 1e5 + 7;
int block, num, l[MAXN], r[MAXN], belong[MAXN];
int n, q;
long long a[MAXN], sum[MAXN], lazy[MAXN];void build()
{
    memset(sum, 0, sizeof(sum));block = sqrt(n);num = n / block;if (n % block)num++;for (int i = 1; i <= num; i++){
    l[i] = (i - 1) * block + 1;r[i] = i * block;}r[num] = n;for (int i = 1; i <= n; i++)belong[i] = (i - 1) / block + 1;for (int i = 1; i <= num; i++){
    for (int j = l[i]; j <= r[i]; j++)sum[i] += a[j];}
}void debug()
{
    for (int i = 1; i <= num; i++)cout << sum[i] << " ";cout << endl;for (int i = 1; i <= num; i++)cout << lazy[i] << " ";cout << endl;
}
void update(int x, int y, long long z)
{
    if (belong[x] == belong[y]){
    for (int i = x; i <= y; i++){
    a[i] += z;sum[belong[x]] += z;}return;}for (int i = x; i <= r[belong[x]]; i++){
    a[i] += z;sum[belong[x]] += z;}for (int i = belong[x] + 1; i < belong[y]; i++){
    lazy[i] += z;}for (int i = l[belong[y]]; i <= y; i++){
    a[i] += z;sum[belong[y]] += z;}
}long long ask(int x, int y)
{
    long long res = 0;if (belong[x] == belong[y]){
    for (int i = x; i <= y; i++){
    res += a[i] + lazy[belong[x]];}return res;}for (int i = x; i <= r[belong[x]]; i++){
    res += a[i] + lazy[belong[x]];}for (int i = belong[x] + 1; i < belong[y]; i++){
    res += sum[i] + 1l * lazy[i] * block;}for (int i = l[belong[y]]; i <= y; i++){
    res += a[i] + lazy[belong[y]];}return res;
}
int main()
{
    while (scanf("%d%d", &n, &q) != EOF){
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);build();memset(lazy, 0, sizeof(lazy));for (int i = 0; i < q; i++){
    char op[10];int x, y;long long z;scanf("%s", op);//debug();if (op[0] == 'Q'){
    scanf("%d%d", &x, &y);printf("%lld\n", ask(x, y));}else{
    scanf("%d%d%lld", &x, &y, &z);update(x, y, z);}}}
}

线段树代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;typedef long long ll;
struct _Node {
    int l, r;ll sum;int mid() {
     return (l + r) / 2; }
};
const int MAXN = 100005;
_Node tree[MAXN << 2];
ll lazy[MAXN << 2];
ll value[MAXN];void push_up(int root) {
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void push_down(int root, int len) {
     //更新lazyif (lazy[root]) {
    lazy[root << 1] += lazy[root];lazy[root << 1 | 1] += lazy[root];tree[root << 1].sum += lazy[root] * (len - len / 2);tree[root << 1 | 1].sum += lazy[root] * (len / 2);lazy[root] = 0;}
}void init(int root, int l, int r) {
    tree[root].l = l;tree[root].r = r;if (l == r) {
    tree[root].sum = value[l];return;}init(root << 1, l, (l + r) / 2);init(root << 1 | 1, (l + r) / 2 + 1, r);push_up(root);
}void update(int root, int l, int r, int value) {
    if (tree[root].l == l && tree[root].r == r) {
    lazy[root] += value;tree[root].sum += (ll)(r - l + 1) * value;return;}if (tree[root].l == tree[root].r) {
    return;}int mid = tree[root].mid();push_down(root, tree[root].r - tree[root].l + 1);if (l > mid)update(root << 1 | 1, l, r, value);else if (r <= mid)update(root << 1, l, r, value);else {
    update(root << 1, l, mid, value);update(root << 1 | 1, mid + 1, r, value);}push_up(root);
}ll query(int root, int l, int r) {
    if (tree[root].l == l && tree[root].r == r) {
    return tree[root].sum;}int mid = tree[root].mid();push_down(root, tree[root].r - tree[root].l + 1);if (l > mid) {
    return query(root << 1 | 1, l, r);} else if (r <= mid) {
    return query(root << 1, l, r);} else {
    return query(root << 1, l, mid) + query(root << 1 | 1, mid + 1, r);}
}
int main() {
    int n, m, a, b, c;char op[10];while (scanf("%d%d", &n, &m) != EOF) {
    memset(lazy, 0, sizeof(lazy));for (int i = 1; i <= n; ++i)scanf("%lld", &value[i]);init(1, 1, n);for (int i = 0; i < m; ++i) {
    scanf("%s", op);scanf("%d%d", &a, &b);if (op[0] == 'Q') {
    if (a > b)swap(a, b);printf("%lld\n", query(1, a, b));} else {
    scanf("%d", &c);update(1, a, b, c);}}}return 0;
}