线段树详解

明天写，今天早点睡觉了。

睡不着，今天晚上写完吧

首先从数组开始理解，现在给定一个数组，我们需要对它进行一些操作，例如单点修改与单点查询，求一段区间的和或者是最大最小值，又或者是乘积，以及对一段区间进行一定的操作，例如对这一段区间的每个元素都加上一个值。
最普通的操作：单点修改，单点查询直接根据下标，这样只需要O(1)的时间，区间的修改查询通过一次遍历区间求得，需要O(n)的时间。
第二种操作就是利用前缀数组，就是把地一个元素到第i个元素的和用一个数组a[]存起来，这样我们对一段区间和的查询就只需要
O(1)的时间的，单点查询只需将a[i]-a[i-1]即可，这里也是O(1)的时间，但是进行修改操作是则需要O(n)的时间，这里时间复杂度就不解释了。
最后就是线段树，线段树是一总折中操作，它的修改查询时间都是O(logn)。
例如一个数组A[1,2,3,4,5];

模板代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#define int long long
#define ll long long
#define FO(n) for(int i=1;i<=(n);i++)
using namespace std;
const int maxn=1e6;
typedef struct SEG_T{
    int l,r,mid,tag;
    ll sum;
}SEG_T;
SEG_T t[maxn<<2];
int v[maxn];
void pushup(int k){
    t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
   // printf("%d《---》%d==%lld\n",t[k].l,t[k].r,t[k].sum);
}
void pushdown(int k){
    if(t[k].l==t[k].r||!t[k].tag)return;
    t[k<<1].sum+=t[k].tag*(t[k<<1].r-t[k<<1].l+1);
    t[k<<1|1].sum+=t[k].tag*(t[k<<1|1].r-t[k<<1|1].l+1);
    t[k<<1].tag+=t[k].tag;
    t[k<<1|1].tag+=t[k].tag;
    t[k].tag=0;
}
void build(int k,int l,int r){
    t[k].l=l,t[k].r=r,t[k].mid=(l+r)>>1;
    if(t[k].l==t[k].r){
        t[k].sum=v[l];
      //  printf("%d《---》%d==%lld\n",l,r,t[k].sum);
        t[k].tag=0;
        return;
    }
    build(k<<1,l,t[k].mid);
    build(k<<1|1,t[k].mid+1,r);
    pushup(k);
}
void update(int k,int index,int value){
    if(t[k].l==t[k].r){
        t[k].sum+=value;
        return;
    }
    pushdown(k);
    if(index<=t[k].mid)update(k<<1,index,value);
    if(index>t[k].mid)update(k<<1|1,index,value);
    pushup(k);
    return;
}
void update(int k,int l,int r,int value){
    if(t[k].r<l||t[k].l>r)return ;
    if(t[k].l>=l&&t[k].r<=r){
        t[k].sum+=value*(t[k].r-t[k].l+1);
        t[k].tag+=value;
        return;
    }
    pushdown(k);
    if(l<=t[k].mid)update(k<<1,l,r,value);
    if(r>t[k].mid)update(k<<1|1,l,r,value);
    pushup(k);
}
ll query(int k,int index){
    if(index<t[k].l||index>t[k].r)return 0;
    if(t[k].l==t[k].r){
        return t[k].sum;
    }
    pushdown(k);
    if(index<=t[k].mid)return query(k<<1,index);
    else return query(k<<1|1,index);
}
ll query(int k,int l,int r){
    if(t[k].r<l||t[k].l>r)return 0;
    if(t[k].l>=l&&t[k].r<=r){
        return t[k].sum;
    }
    pushdown(k);
    
    ll res=0;
    if(l<=t[k].mid)res+=query(k<<1,l,r);
    if(r>t[k].mid)res+=query(k<<1|1,l,r);
    return res;
}
int n,q;
int a,b,c,d;
signed main(){
    while (scanf("%lld%lld",&n,&q)!=EOF)
    {
        FO(n)scanf("%lld",&v[i]);
        build(1,1,n);
        FO(q){
            scanf("%lld%lld",&a,&b);
            if(a==1){
                scanf("%lld%lld",&c,&d);
                update(1,b,c,d);
            }
            if(a==2)printf("%lld\n",query(1,b));
        }
    }
}