[POJ3468]A Simple Problem with Integers

这是一道区间查询与修改的题目,首选树状数组线段树,但是根据《算法竞赛进阶指南》的思想,我们不妨思考一下树状数组的解法。👀

首先对不变量$A_{i}$求前缀和,最后在区间上累加改变量即可。那么问题来了,树状数组仅支持单点查询与修改,如何强行让它支持区间上的操作呢?

我们假设$t[i]$数组储存着每个点的改变量,那么对于$[1,x]$区间,有改变量$$change = \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i}b[j]=\sum\limits_{i=1}^{x}(x-i+1)*b[i]=(x+1)\sum\limits_{i=1}^{x}b[i]-\sum\limits_{i=1}^{x}i*b[i]$$

对应的我们维护两个树状数组,一个用于维护$(x+1)\sum\limits_{i=1}^{x}b[i]$,而另一个用于维护$\sum\limits_{i=1}^{x}i*b[i]$。

下面给出参考代码:

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;

int n,m;

ll sum[MAXN];
ll tree[2][MAXN];

int lowbit(int x) {
    return x & -x;
}

void add(int k,int x,ll data) {
    for (; x <= n; x += lowbit(x))
        tree[k][x] += data;
}

ll query(int k,int x) {
    ll ret = 0;

    for (; x; x -= lowbit(x))
        ret += tree[k][x];

    return ret;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    int temp;
    for (int i = 1; i <= n; ++i) {
        cin >> temp;

        sum[i] = sum[i - 1] + temp;
    }

    char op;
    int l,r,d;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
        if (op == 'C') {
            cin >> l >> r >> d;

            add(0, l, d);
            add(0, r + 1, -d);
            add(1, l, l * d);
            add(1, r + 1, (r + 1) * -d);
        } else {
            cin >> l >> r;

            cout << sum[r] + (r + 1) * query(0, r) - query(1, r) - sum[l - 1] - l * query(0, l - 1) + query(1, l - 1) << endl;
        }
    }
 
    return 0;
}

当然,这道题目理所应当可以用线段树做,参考代码如下:

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;

struct SegmentTree{
    int l,r;
    int data;
    int add;
}t[MAXN << 2];

int n,m;
int a[MAXN];

void build(int p,int l,int r) {
    t[p].l = l;
    t[p].r = r;

    if (l == r) {
        t[p].data = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    t[p].data = t[p << 1].data + t[p << 1 | 1].data;
}

void downpush(int p) {
    if (t[p].add) {
        t[p << 1].data += t[p].add * (t[p << 1].r - t[p << 1].l + 1);
        t[p << 1 | 1].data += t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
        t[p << 1].add += t[p].add;
        t[p << 1 | 1].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p,int l,int r,int d) {
    if (l <= t[p].l && r >= t[p].r) {
        t[p].data += d * (t[p].r - t[p].l + 1);
        t[p].add += d;

        return;
    }

    downpush(p);

    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        change(p << 1, l, r, d);
    if (r > mid)
        change(p << 1 | 1, l, r, d);

    t[p].data = t[p << 1].data + t[p << 1 | 1].data;
}

ll query(int p,int l,int r) {
    ll ret = 0;
    
    if (l <= t[p].l && r >= t[p].r)
        return t[p].data;

    downpush(p);

    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        ret += query(p << 1, l, r);
    if (r > mid)
        ret += query(p << 1 | 1, l, r);

    return ret;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) 
        cin >> a[i];

    build(1, 1, n);

    char op;
    int l,r,d;
    for (int i = 1; i <= m; ++i) {
        cin >> op;
        if (op == 'C') {
            cin >> l >> r >> d;

            change(1, l, r, d);
        } else {
            cin >> l >> r;

            cout << query(1, l, r) << endl;
        }
    }
 
    return 0;
}

(线段树的代码就是长

Last modification:May 8th, 2019 at 09:58 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

One comment

  1. Kuludu

    👀

Leave a Comment Cancel reply