洛谷——P3372 【模板】线段树 1

题目

P3372 【模板】线段树 1

题目描述

如题，已知一个数列 { a i } \{a_i\} {ai​}，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数 $a_i$，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 $[x,y]$ 内每个数加上 $k$。
2. 2 x y：输出区间 $[x,y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

11
8
20

说明/提示

对于 $15\%$ 的数据：$n\le 8$，$m\le 10$。
对于 $35\%$ 的数据：$n\le {10}^3$，$m\le {10}^4$。
对于 $100\%$ 的数据：$1\le n,m\le {10}^5$，$a_i,k$ 为正数，且任意时刻数列的和不超过 $2\times 10^{18}$。

【样例解释】

代码

#include <bits/stdc++.h>
#define ll long long int 
#define maxn 100001
using namespace std;
struct Tree{ll l,r,d;//节点区间//区间和 
}node[maxn<<2];//第几个节点 
int n,//n个数 m,//m个操作x;//操作数 
ll	s,t,//区间lazy[maxn<<2],//懒信息 d[maxn],//序列 k;//加到区间的数 
void build(int x,ll l,ll r){//建立线段树 node[x].l=l,node[x].r=r;if(l==r){node[x].d=d[l];return;}ll mid=l+r>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);node[x].d=node[x<<1].d+node[x<<1|1].d;
}
void update(int x){//处理懒信息 if(lazy[x]==0)return;//没有懒信息 ll mid=node[x].r+node[x].l>>1;//一个是节点序号，一个是区间 node[x<<1].d+=(mid-node[x].l+1)*lazy[x];	lazy[x<<1]+=lazy[x];//左区间懒信息的更新 node[x<<1|1].d+=(node[x].r-mid)*lazy[x];	lazy[x<<1|1]+=lazy[x];//右区间懒信息更新 lazy[x]=0;//处理后清零 
}
ll find(int x,ll l,ll r,ll left,ll right){//找到区间和 if(l>=left&&r<=right)return node[x].d;//是该区间 update(x);//找区间过程处理懒信息 ll mid=l+r>>1,he=0;if(left<=mid)he+=find(x<<1,l,mid,left,right);//左区间 if(mid<right)he+=find(x<<1|1,mid+1,r,left,right);//右区间 return he; //左右区间之和 
}
void add(int x,ll l,ll r,ll left,ll right,ll k){//给区间加k,就是(r-l+1)*k if(l>=left&&r<=right){//在区间内就加 node[x].d+=(r-l+1)*k;lazy[x]+=k;return;}update(x);//明确区间的过程，顺带解决前面留下的懒信息 ll mid=l+r>>1;if(left<=mid)add(x<<1,l,mid,left,right,k);if(mid<right)add(x<<1|1,mid+1,r,left,right,k);node[x].d=node[x<<1].d+node[x<<1|1].d;//重新计算每个节点的区间和=左右区间的和 
}
void view(int s,int t,string ss,int k){cout<<s<<"到"<<t<<"\t"<<ss<<k<<endl; queue<int> q1,q2;q1.push(1);while(!q1.empty()){int x;while(!q1.empty()){x=q1.front();q1.pop();if(x==0||node[x].l==0||node[x].r==0){cout<<endl;return;}cout<<x<<"("<<node[x].l<<","<<node[x].r<<")"<<node[x].d<<","<<lazy[x]<<"\t";q2.push(x<<1),q2.push(x<<1|1);}cout<<endl;while(!q2.empty()){x=q2.front();q2.pop();q1.push(x);}}cout<<endl;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>d[i];build(1,1,n);//view(0,0,"开始",0);for(int i=1;i<=m;i++){cin>>x>>s>>t;if(x==2){cout<<find(1,1,n,s,t)<<endl;//view(s,t,"find",k);}else if(x==1){cin>>k;add(1,1,n,s,t,k);//view(s,t,"add",k);}}//view(0,0,"结束",0);return 0;
}

技术细节

1.分清节点序号和区间
2.注意输入数据范围a、i 、k 为正数，且任意时刻数列的和不超过 2×10
18 。正数，小于2*10^8，必须用long long int。