poj 3648 线段树成段更新

线段树成段更新需要用到延迟标记（或者说懒惰标记），简单来说就是每次更新的时候不要更新到底，用延迟标记使得更新延迟到下次需要更新or询问到的时候。延迟标记的意思是：这个区间的左右儿子都需要被更新，但是当前区间已经更新了。其主要使用了Lazy思想。

Lazy思想：lazy－tag思想，记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。
在此通俗的解释Lazy(t偷懒)的意思，比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，它的节点标记为rt，这时tree[rt].l == a && tree[rt].r == b 这时我们可以一步更新此时rt节点的sum[rt]的值，sum[rt] += c * (tree[rt].r - tree[rt].l + 1)，注意关键的时刻来了，如果此时按照常规的线段树的update操作，这时候还应该更新rt子节点的sum[]值，而Lazy思想恰恰是暂时不更新rt子节点的sum[]值，到此就return，直到下次需要用到rt子节点的值的时候才去更新，这样避免许多可能无用的操作，从而节省时间。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<algorithm>

const int MAXN = +;

typedef long long LL;

using namespace std;

struct Tnode{

    int b, e;

    LL sum;     //当前区间和

    LL mark;   //延迟标记

};

Tnode tree[*MAXN];

int n;

void Build(int v, int b, int e){

    tree[v].b = b, tree[v].e = e;

    tree[v].sum=tree[v].mark = ;

    if (b < e){

        int mid = (b + e) >> ;

        Build( * v + , b, mid);

        Build( * v + , mid + , e);

    }

}

void update(int v, int l, int r, LL value){

    if (l == tree[v].b&&r == tree[v].e){

        tree[v].mark += value;     //该区间每个数都要增加value，它的子区间可以先不更新(Lazy)

        return;          //直接返回了

    }

    tree[v].sum += value*(r - l + );   //将增加的值更新进去

    int mid = (tree[v].b + tree[v].e) >> ;

    if (r <= mid)

        update( * v + , l, r, value);

    else if (l > mid)

        update( * v + , l, r, value);

    else{

        update( * v + , l, mid, value);

        update( * v + , mid + , r, value);

    }

}

LL Qurrey(int v, int l, int r){

    if (tree[v].b==l&&tree[v].e==r)

        return tree[v].sum+(r-l+)*tree[v].mark;

    if (tree[v].mark != ){  //之前欠的债现在要还了

        //如果当前区间mark不为0，则将它传递给子区间

        tree[ * v + ].mark += tree[v].mark;

        tree[ * v + ].mark += tree[v].mark;

        tree[v].sum += tree[v].mark*(tree[v].e-tree[v].b+);

        tree[v].mark = ;

    }

    int mid = (tree[v].b + tree[v].e) >> ;

    if (r <= mid)

        return Qurrey( * v + , l, r);

    else if (l > mid)

        return Qurrey( * v + , l, r);

    else

        return Qurrey( * v + , l, mid) + Qurrey( * v + , mid + , r);

}

int main(){

    long long x;

    int a, b,i,q;

    char ch;

    scanf("%d%d", &n, &q);

    Build(, , n);

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

        scanf("%lld", &x);

        update(, i, i, x);

    }

    while (q--){

        cin >> ch;

        scanf("%d%d", &a, &b);

        if (ch == 'Q')

            printf("%lld\n", Qurrey(, a, b));

        else{

            scanf("%lld", &x);

            update(, a, b, x);

        }

    }

    return ;

}

巴特西

poj 3648 线段树成段更新

最新文章

热门文章