Segment Tree + lazy tag (線段樹+懶標記)

區間改值用segment tree+lazy tag實作時，複雜度還是只有O(lg N)
指標版的線段樹

模板題：IOICamp Judge 23

//Segment Tree (pointer), take sum as example
// lazy tag

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <assert.h>   // modify 's   assert
using namespace std;

struct Node {
    long long int val, tag;
    Node *lc, *rc;
    Node(){
        tag=0;
        val=0;
        lc = NULL;
        rc = NULL;
    }
    void pull () {
        val = lc->val + rc->val;
    }
};

const int MAX_N = 100003;

int n, v[MAX_N+1];

void input(int m) {
    memset(v,0,sizeof(v));
    for (int x=1;m>=x;x++) scanf("%d",&v[x]);
}

Node* build(int L, int R) {
    Node *node = new Node();
    if (L==R) {
        node->val = v[L];
        return node;
    }
    int mid = (L+R) >> 1;
    node->lc = build(L,mid);
    node->rc = build(mid+1,R);
    node->pull();
    return node;
}

void push(Node* node, int L,int R) {
    if (!node->tag) return;
    if (L!=R) {   //check leaf
        int mid= (L+R) >> 1;
        node->lc->tag += node->tag;
        node->rc->tag += node->tag;
        node->lc->val += node->tag * (mid - L +1);   //因為tag��表示"之後"的要~~~，所以目前的要處理一下 
        node->rc->val += node->tag * (R - mid);
    }
    node->tag = 0;
}

void modify( Node* node, int L, int R, int ql, int qr,long long int d) {    // 區間修改  |  d : value
    if (ql > R || qr < L) return;
    if (ql<=L && R<=qr) {
        node->tag += d;
        node->val += d*(R-L+1);
        return;
    }
    
    push(node,L,R);
    int mid = (L+R) >> 1;
    modify(node->lc, L,mid,ql,qr,d);
    modify(node->rc,mid+1,R,ql,qr,d);
    node->pull();
}

long long int query(Node* node, int L,int R, int ql, int qr) {
    if (ql > R || qr< L)  return 0;   //mission impossible
    if (ql<=L && R<= qr) return node->val;
    push(node,L,R);
    int mid = (L+R) >> 1;
    return query(node->lc,L,mid,ql,qr) + query(node->rc, mid+1, R ,ql,qr);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int q;
        scanf("%d %d",&n,&q);
        input(n);
        Node* root = build(1,n);
        for (int i=0;q>i;i++) {
            string k;
            cin >> k;
            if (k=="add") {   //改區間值(加法) 
                int ql,qr,val;
                scanf("%d %d %d",&ql,&qr,&val);
                modify(root,1,n,ql,qr,val);
            }
            else if (k=="query") {
                int l,r;
                scanf("%d %d",&l,&r);
                printf("%lld\n",query(root,1,n,l,r));
            }
        }
    }
    
}