（模板）线段树1

```cpp #include<map> #include<cmath> #include<queue> #include<string> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int N=800001; int lazy[N],a[N]; int x,y,z,n,m; ll s[N]; template <class sjy> inline void read(sjy &x){ sjy f=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} x*=f; } void pushdown(int o,int left,int right){ if(lazy[o]==0) return ; int mid=(left+right)>>1; if(left==right) return ; s[o<<1]+=lazy[o]*(mid-left+1); lazy[o<<1]+=lazy[o]; s[o<<1|1]+=lazy[o]*(right-mid); lazy[o<<1|1]+=lazy[o]; lazy[o]=0; } ll search(int o,int left,int right){ pushdown(o,left,right); if(x<=left&&y>=right) return s[o]; ll sum=0; int mid=(left+right)>>1; if(x<=mid) sum=sum+search(o<<1,left,mid); if(y>mid) sum=sum+search(o<<1|1,mid+1,right); return sum; } void change(int o,int left,int right){ pushdown(o,left,right); if(x<=left&&y>=right){ s[o]=s[o]+z*(right-left+1); lazy[o]=z; return ; } int mid=(left+right)>>1; if(x<=mid) change(o<<1,left,mid); if(y>mid) change(o<<1|1,mid+1,right); s[o]=s[o<<1]+s[o<<1|1]; } void build(int o,int left,int right){ if(left==right){ s[o]=a[left]; return ; } int mid=(left+right)>>1; build(o<<1,left,mid); build(o<<1|1,mid+1,right); s[o]=s[o<<1]+s[o<<1|1]; } int main(){ int z; read(n),read(m); for(register int i=1;i<=n;i++) read(a[i]); build(1,1,n); } ```