Poj-P3468题解【线段树】

本文为原创，转载请注明：http://www.cnblogs.com/kylewilson/

题目出处：

http://poj.org/problem?id=3468

题目描述：

给N个数A₁, A₂, ... , A_N. 你需要处理两种操作，一种操作是在一个区间上每个数都增加一个数，别一种操作是查询一个区间所有数的和

输入

第一行两个数N, Q, 1 ≤ N,Q ≤ 100000

第二行N个数，数组初始值A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.

接着Q行，表示Q次操作"C a b c" 表示区间A_a, A_a₊₁, ... , A_b.，第个数增加c, -10000 ≤ c ≤ 10000.

"Q a b" 表示查询区间A_a, A_a₊₁, ... , A_b之和

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

思路分析：

首先分析数据规模，如果有简单模拟算法，时间复杂度O(N*Q)，肯定会超时；

看题目需求，每次输入都是对区间进行增加或者查询等操作，所以也必须用区间操作算法来解决；

此文以线段树来解决，树状数组也很适合解决此类问题。事实证明能用树状数组解决的都可以用线段树来解决，反之则不行；

线段树维护区间信息，而树状数组维护前缀和信息；

如上图P1.1，对于增加操作如(a=0, b=2, c=1)，需要对[0,2]区间每个点进行增加，但如果递归所有子树去增加操作，就退化成了线性；

所以遍历到[0,2]区间时，只对该点操作，并记录以该点以根的子树，应该增加的值，先记录，下次遍历到子树再执行操作

如上图P1.2，对[0,2]执行了操作，再子树还没有增加，如果下次查询子树则数据错误，所以每次在执行增加或者查询操作的时候，就把上次遗留下来的数据给补上，也就是所谓的Lazy思想。

每个树节点主要记录如下信息：

left: 区间左起点

right: 区间右终点

total: 区间和

childrenExtra: 子树还应该额外增加的值

lson, rson: 左右子树

注：因题目数据量大，输入输出用scanf, printf，如果用cin, cout则会超时。

C++源码如下：

github: https://github.com/Kyle-Wilson1/Poj/tree/master/P3468

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

struct SegmentTree {

    long long left, right, total, childrenExtra;

    SegmentTree *lson, *rson;

};

long long regionLength(SegmentTree *tree) {

    return tree->right - tree->left + 1;

}

void updateChildren(SegmentTree *root) {

    if (root->lson != NULL && root->rson != NULL && root->childrenExtra != 0) {

        root->lson->total += root->childrenExtra * regionLength(root->lson);

        root->lson->childrenExtra += root->childrenExtra;

        root->rson->total += root->childrenExtra * regionLength(root->rson);

        root->rson->childrenExtra += root->childrenExtra;

        root->childrenExtra = 0;

    }

}

SegmentTree *buildTree(vector<long long> &num, long long l, long long r) {

    if (l > r) {

        return NULL;

    }

    if (l == r) {

        SegmentTree *root = new SegmentTree;

        root->left = l;

        root->right = r;

        root->total = num[l];

        root->childrenExtra = 0;

        root->lson = NULL;

        root->rson = NULL;

        return root;

    }

    SegmentTree *root = new SegmentTree;

    root->left = l;

    root->right = r;

    root->childrenExtra = 0;

    long long mid = (l + r) >> 1;

    root->lson = buildTree(num, l, mid);

    root->rson = buildTree(num, mid + 1, r);

    root->total = root->lson->total + root->rson->total;

    return root;

}

void addRegion(SegmentTree *root, long long regionLeft, long long regionRight, long long addNum) {

    if (root == NULL || root->right < regionLeft || root->left > regionRight) {

        return;

    }

    if (root->left >= regionLeft && root->right <= regionRight) {

        root->total += addNum * regionLength(root);

        if (root->left < root->right)root->childrenExtra += addNum;

        return;

    }

    updateChildren(root);

    addRegion(root->lson, regionLeft, regionRight, addNum);

    addRegion(root->rson, regionLeft, regionRight, addNum);

    root->total = root->lson->total + root->rson->total;

}

void queryRegion(SegmentTree *root, long long regionLeft, long long regionRight, long long &sum) {

    if (root == NULL || root->right < regionLeft || root->left > regionRight) {

        return;

    }

    if (root->left >= regionLeft && root->right <= regionRight) {

        sum += root->total;

        return;

    }

    updateChildren(root);

    queryRegion(root->lson, regionLeft, regionRight, sum);

    queryRegion(root->rson, regionLeft, regionRight, sum);

}

int main() {

    ifstream fin("a.in");

    ofstream fout("a.out");

    long long n, q, i, a, b, c;

    char type[2];

    SegmentTree *root;

//    scanf("%lld%lld", &n, &q);

    fin >> n >> q;

    vector<long long> num(n, 0);

    for (i = 0; i < n; i++) {

//        scanf("%lld", &num[i]);

        fin >> num[i];

    }

    n--;

    root = buildTree(num, 0, n);

    for (i = 0; i < q; i++) {

//        scanf("%s", type);

        fin >> type;

        if (type[0] == 'C') {

//            scanf("%lld%lld%lld", &a, &b, &c);

            fin >> a >> b >> c;

            addRegion(root, a - 1, b - 1, c);

        } else {

//            scanf("%lld%lld", &a, &b);

            fin >> a >> b;

            long long sum = 0;

            queryRegion(root, a - 1, b - 1, sum);

//            printf("%lld\n", sum);

            fout << sum << endl;

        }

    }

    return 0;

}

巴特西