线段树

线段树是一个神奇的数据结构，可以解决好多问题。
我第一次写的时候，写了3500+，结果，是错的。。。
我当时就笑了。。。
然后参（chao）考（xi）了某位大神的代码，才最终写出来了一份2000+的线段树。
话说，线段树这种数据结构支持在logn的时间内区间修改，区间求和，区间求最值等，是一种比较优秀的nlogn的数据结构。
我的代码比较简陋，以后可能还会更改。
下来贴代码：（这个是【洛谷P3372 线段树1】的代码）

#include<bits/stdc++.h>
#define ll long long
#define inf 9223372036854775807
using namespace std;
int n,m;
ll num[100001];
struct node{
    int l,r;
    ll sum,mx,mn,lazy;
}t[400001];
void pushup(int i){//更新一个区间，为了减少代码长度写了这个
    t[i].sum=t[i*2].sum+t[i*2+1].sum;
    t[i].mx=max(t[i*2].mx,t[i*2+1].mx);
    t[i].mn=min(t[i*2].mn,t[i*2+1].mn);
}
void update(int i,ll v){
    t[i].sum+=v*(t[i].r-t[i].l+1);
    t[i].mx+=v;
    t[i].mn+=v;
    t[i].lazy+=v;
}
void pushdown(int i){
    if(t[i].lazy!=0){
        update(i*2,t[i].lazy);
        update(i*2+1,t[i].lazy);
        t[i].lazy=0;
    }
}
void build(int i,int left,int right){
    t[i].l=left;
    t[i].r=right;
    if(left==right){
        t[i].sum=num[left];
        t[i].mn=num[left];
        t[i].mx=num[left];
        return;
    }
    int mid=(t[i].l+t[i].r)/2;
    build(i*2,left,mid);
    build(i*2+1,mid+1,right);
    pushup(i);
}
void add(int i,int left,int right,ll v){
    if(t[i].l==left&&t[i].r==right){
        update(i,v);
        return;
    }
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(mid>=right)add(i*2,left,right,v);
    else if(mid+1<=left)add(i*2+1,left,right,v);
    else{
        add(i*2,left,mid,v);
        add(i*2+1,mid+1,right,v);
    }
    pushup(i);
}
ll qsum(int i,int left,int right){
    if(t[i].l==left&&t[i].r==right){
        return t[i].sum;
    }
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(mid>=right)return qsum(i*2,left,right);
    else if(mid+1<=left)return qsum(i*2+1,left,right);
    else return qsum(i*2,left,mid)+qsum(i*2+1,mid+1,right);
}
ll qmax(int i,int left,int right){
    if(t[i].l==left&&t[i].r==right){
        return t[i].mx;
    }
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(mid>=right)return qmax(i*2,left,right);
    else if(mid+1<=left)return qmax(i*2+1,left,right);
    else return max(qmax(i*2,left,right),qmax(i*2+1,left,right));
}
ll qmin(int i,int left,int right){
    if(t[i].l==left&&t[i].r==right){
        return t[i].mn;
    }
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(mid>=right)return qmin(i*2,left,right);
    else if(mid+1<=left)return qmin(i*2+1,left,right);
    else return min(qmin(i*2,left,right),qmin(i*2+1,left,right));
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&num[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int t;
        scanf("%d",&t);
        if(t==1){//区间加
            int x,y;
            ll k;
            scanf("%d %d %lld",&x,&y,&k);
            add(1,x,y,k);
        }
        else{//区间求和
            int x,y;
            scanf("%d %d",&x,&y);
            printf("%lld
",qsum(1,x,y));
        }
    }
    return 0;
}