懒标记

懒标记, 是线段树解决区间更新问题的利器。
听完y总的视频， 实在被该算法设计震撼到了， 真的是一个很懒的算法哈哈。

拙见

下面讲下个人对懒标记的拙见。
顾名思义， 懒标记， 就是以偷懒闻名的。

特性

线段树的查询， 从根节点出发， 如果走到某个节点， 该节点的左右区间满足查询要求， 直接可以返回结果。
懒标记就是利用这一特性， 如果更新区间值， 需要从上往下更新（push down）。只要更新到达某个节点的左右区间满足更新需求， 就停止更新，剩下的区间用一个标记add来表示，等以后需要用到再更新。
实在是够懒的哈哈。

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static long[] a;
    static Node[] tr;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]), m = Integer.valueOf(ss[1]);
        a = new long[n + 1];
        tr = new Node[n * 4];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Long.valueOf(ss[i - 1]);
        }

        while(m -- > 0){
            ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[1]), b = Integer.valueOf(ss[2]);
            switch("ss[0]"){
                case "Q":
                    log.write(query(1, a, b) + "\n");
                    break;
                case "C":
                    modify(1, a, b, Integer.valueOf(ss[3]);
                    break;
            }
        }
        log.flush();

    }

    public static void modify(int u, int l, int r, int add){
        if(tr[u].l >= l && tr[u].r <= r){
            tr[u].sum += (long)(tr[u].r - tr[u].l + 1) * add;
            tr[u].add += add;
        }else{
            pushDown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            modify(u << 1, l, r, add);
            modify(u << 1 | 1, l, r, add);
            pushUp(u);
        }
    }

    public static long query(int u, int l, int r){
        if(tr[u].l >= l &&tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        pushDown(u);
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        long res = 0;
        if(l <= mid) res = query(u << 1, l, r);
        if(r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }

    public static void build(int u, int l, int r){
        if(l == r){
            tr[u] = new (l, r, a[l]);
        }else{
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(tr[u << 1], l, mid); build(tr[u << 1 | 1], mid + 1, r);
            pushUp(u);
        }
    }

    public static void pushUp(int u){
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }

    public static void pushDown(int u){
        if(tr[u].add != 0){
            Node l = tr[u << 1], r = tr[u << 1 | 1];
            l.add = tr[u].add; l.sum = (long)tr[u].add * (l.r - l.l + 1);
            r.add = tr[u].add; r.sum = (long)tr[u].add * (r.r - r.l + 1);
            tr[u].add = 0;
        }
    }



    static class Node{
        int l, r;
        long sum, add;
        Node(int l, int r, long sum){
            this.l = l; this.r = r; this.sum = sum;
        }
    }
}