线段树模板 CDOJ1057

UESTCOJ不知道为什么进不去了哇

跟着叉姐的算法讲堂写的板子

叉姐的思路真的好清晰啊，一定是练习的多并且理解的够深了

希望自己也可以每天进步一点点吧

代码：

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]";

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int maxn = 1e5+;

int n,a[maxn],q;

struct node{

    int l,r;

    long long sum,lazy;

    void update(long long x){

        sum+=1ll*(r-l+)*x;

        lazy+=x;

    }

}tree[maxn*];

void push_up(int x){

    tree[x].sum=tree[x<<].sum+tree[x<<|].sum;

}

void push_down(int x){

    int lazyval=tree[x].lazy;

    if(lazyval){

        tree[x<<].update(lazyval);

        tree[x<<|].update(lazyval);

        tree[x].lazy=;

    }

}

void build(int x,int l,int r){

    tree[x].l=l,tree[x].r=r;

    tree[x].sum=tree[x].lazy=;

    if(l==r){

        tree[x].sum=a[l];

    }else{

        int mid=(l+r)/;

        build(x<<,l,mid);

        build(x<<|,mid+,r);

        push_up(x);

    }

}

void update(int x,int l,int r,long long val){

    int L=tree[x].l,R=tree[x].r;

    if(l<=L&&R<=r){

        tree[x].update(val);

    }else{

        push_down(x);

        int mid=(L+R)/;

        if(mid>=l) update(x<<,l,r,val);

        if(r>mid) update(x<<|,l,r,val);

        push_up(x);

    }

}

long long query(int x,int l,int r){

    int L=tree[x].l,R=tree[x].r;

    if(l<=L&&R<=r){

        return tree[x].sum;

    }else{

        push_down(x);

        long long ans=;

        int mid=(L+R)/;

        if(mid>=l) ans+=query(x<<,l,r);

        if(r>mid) ans+=query(x<<|,l,r);

        push_up(x);

        return ans;

    }

}

int main(){

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    }

    scanf("%d",&q);

    for(int i=;i<=q;i++){

        int l,r,val;

        scanf("%d%d%d",&l,&r,&val);

        update(,l,r,val);

        printf("%lld\n",query(,l,r));

    }

}