Tags

, ,

题目大意：对某给定数组可进行多次如下操作：

  • 计算给定区间的和并输出
  • 给定区间的每个数均增加某个值

这道题是一道典型的Lazy线段树，之前从来没接触过，今天算是小有收获~ 最后830ms过了

线段树是一种二叉搜索树，对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

因此，可以很方便的用一个一维数组来存取线段树，#define两个宏就可以很方便地访问某个节点的左右子节点。不过，使用这种方法需要注意数组的空间不只2N，一般要开4N。当然，用指针做也是非常方便的。

Lazy线段树的思想是遇到更改操作时，不着急更新每个节点的值，需要用到具体值时再更新。在本题中每个节点添加needAdd字段，对于某一个节点，进行更改(calc)操作时要保证在进行每次更改(calc)操作结束时有：节点对应区间的和=needAdd*节点区间长度 + 节点的值。这样，进行查询操作时，将查询区间关于左右子树分段递归查找，遇到查询区间和节点区间相同则直接返回上面这个式子即可。

 

下面是代码：

#include <stdio.h>
#include <string.h>
#define MAXN 100001

struct segNode
{
    long long val;//sum of numbers
    long long start,end;
    long long needAdd; //lazy
    segNode* left;
    segNode* right;
    segNode(long long _val,long long _start,long long _end,long long _needAdd = 0,segNode* _left = NULL,segNode* _right = NULL)
    {
        val     = _val;
        start   = _start;
        end     = _end;
        needAdd = _needAdd;
        left    = _left;
        right   = _right;
    }
};

long long a[MAXN];

segNode* buildSegTree(long long start,long long end)
{
    if (start == end)
    {
        segNode* newNode = new segNode(a[start],start,start);
        return newNode;
    }
    long long mid = (start + end)/2;
    segNode *root = new segNode(0,start,end);
    root->left  = buildSegTree(start, mid);
    root->right = buildSegTree(mid + 1, end);
    root->val   = root->left->val + root->right->val;
    return root;
}

long long query(segNode* root,long long start,long long end)
{

    if (root->start != start || root->end != end) {
        long long mid = root->left->end;
        if (start > mid) {
            return query(root->right, start, end) +
                        root->needAdd * (end - start + 1);
        }
        if (end <= mid) {
            return query(root->left, start, end) +
                        root->needAdd * (end - start + 1);
        }
        else {
            return query(root->left, start, mid) +
                            query(root->right, mid + 1, end) +
                                root->needAdd * (end - start + 1);
        }
    }
    return root->val + root->needAdd * (end - start + 1);
}
long long calc(segNode* root, long long start,long long end, long long num)
{
    if (root == NULL) {
        return 0;
    }
    if (start < root->start) {
        start = root ->start;
    }
    if (end > root->end) {
        end = root->end;
    }
    if (start <= end) {
        if (start == root->start && root->end == end) {
            root->needAdd += num;
        }
        else {
            root->val = calc(root->left, start, end, num) +
                        calc(root->right, start, end, num);
        }
        return root->val + root->needAdd * (root->end - root->start + 1);
    }

    //root isn't in the range
    return root->val + root->needAdd * (root->end - root->start + 1);
}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    long long n,q;
    scanf("%lld %lld",&n,&q);

    //init A1-An & seg tree's root
    long long sum = 0;
    for (long long i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
        sum += a[i];
    }
    segNode *segTree = buildSegTree(1, n);

    char cmd;
    while (scanf("%c ",&cmd)!=EOF) {
        if (cmd == 'Q') {
            long long start,end;
            scanf("%lld %lld",&start,&end);
            long long ans = query(segTree,start, end);
            printf("%lldn",ans);
        }
        else if (cmd == 'C'){
            long long start,end,num;
            scanf("%lld %lld %lld",&start,&end,&num);
            calc(segTree,start, end, num);
        }
    }
    return 0;
}