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) { //更新lazy
  if (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;
}