建树：
int a[100005],d[100005];
void build(int s,int e,int p){// 建树
// 对区间[s,t]建立线段树，当前根编号为p
if(s==e){
d[p]=a[s];
return ;
}
int m=s+((e-s)>>1);
build(s,m,p*2);
build(m+1,e,p*2+1);// 分割出两个子区间
d[p]=d[p*2]+d[(p*2)+1];
}// d[i]为编号i节点保存的值为d[i]
区间查询：
int find(int l,int r,int s,int e,int p){//区间查询（基础版）
// [l, r] 为查询区间, [s, e] 为当前节点包含的区间, p 为当前节点的编号
if(l<=s&&e<=r){
return d[p];
}// 当前区间为询问区间的子集时直接返回当前区间的和
int mid=s+((e-s)>>1),sum=0;
if(l<=mid)sum+=find(l,r,s,mid,p*2);
// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
if(r>mid)sum+=find(l,r,mid+1,e,p*2+1);
// 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
return sum;
}
int find_change(int l,int r,int s,int e,int p){//区间查询（修改版）
// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
if(l<=s&&e<=r){
return d[p];
}// 当前区间为询问区间的子集时直接返回当前区间的和
int mid=s+((e-s)>>1);
if(b[p]!=0){
d[p*2]+=b[p]*(mid-s+1);
d[p*2+1]+=b[p]*(e-mid);
// 修改当前节点
b[p*2]+=b[p];
b[p*2+1]+=b[p];
// 将标记下传给子节点
b[p]=0;
// 清空当前节点的标记
}
int sum=0;
if(l<=mid)sum+=find_change(l,r,s,mid,p*2);
// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
if(r>mid)sum+=find_change(l,r,mid+1,e,p*2+1);
// 如果右儿子代表的区间[mid+1,r]与询问区间有交集，则递归查询右儿子
return sum;
}
区间修改
void add(int l,int r,int c,int s,int e,int p){//区间修改(区间加上某个值)
// [l, r] 为修改区间, c为被修改的元素的变化量, [s, t] 为当前节点包含的区间
// p为当前节点的编号
if(l<=s&&e<=r){
//d[p]+=(e-s+1)*c;
d[p]+=(e-s+1)*c;
b[p]+=c;
return ;
}// 当前区间为修改区间的子集是直接修改当前值，然后打标记，结束修改
int mid=s+((e-s)>>1);
if(b[p]!=0&&s!=e){
// 若当前节点的标记为空，则更新该节点两个子节点的值和标记值
d[p*2]+=b[p]*(mid-s+1);
d[p*2+1]+=b[p]*(e-mid);
// 修改当前子节点的值
b[p*2]+=b[p];
b[p*2+1]+=b[p];
// 将标记下传给子节点
b[p]=0;
// 清空当前节点的标记
}
if(l<=mid)add(l,r,c,s,mid,p*2);
// 处理左子节点
if(r>mid)add(l,r,c,mid+1,e,p*2+1);
// 处理右子节点
d[p]=d[p*2]+d[p*2+1];
// 修改当前节点的值
}
模板题：P3372 【模板】线段树 1
【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 $k$。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。
第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。
接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：
1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。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
提示
对于 $30%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100%$ 的数据：$1 \le n, m \le {10}^5$。
保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。
【样例解释】
解析及代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,op,x,y,k;
int a[1000005],d[1000005],b[1000005];
// a为原数组，d为线段树数组，b为标记数组
void build(int s,int e,int p){// 建树
// 对区间[s,e]建立线段树，当前根编号为p
if(s==e){
d[p]=a[s];
return ;
}
int mid=s+((e-s)>>1);
build(s,mid,p*2);
build(mid+1,e,p*2+1);// 分割出两个子区间
d[p]=d[p*2]+d[(p*2)+1];
}// d[i]为编号i节点保存的值为d[i]
int find(int l,int r,int s,int e,int p){//区间查询（基础版）
// [l, r] 为查询区间, [s, e] 为当前节点包含的区间, p 为当前节点的编号
if(l<=s&&e<=r){
return d[p];
}// 当前区间为询问区间的子集时直接返回当前区间的和
int mid=s+((e-s)>>1),sum=0;
if(l<=mid)sum+=find(l,r,s,mid,p*2);
// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
if(r>mid)sum+=find(l,r,mid+1,e,p*2+1);
// 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
return sum;
}
void add(int l,int r,int c,int s,int e,int p){//区间修改(区间加上某个值)
// [l, r] 为修改区间, c为被修改的元素的变化量, [s, t] 为当前节点包含的区间
// p为当前节点的编号
if(l<=s&&e<=r){
//d[p]+=(e-s+1)*c;
d[p]+=(e-s+1)*c;
b[p]+=c;
return ;
}// 当前区间为修改区间的子集是直接修改当前值，然后打标记，结束修改
int mid=s+((e-s)>>1);
if(b[p]!=0&&s!=e){
// 若当前节点的标记为空，则更新该节点两个子节点的值和标记值
d[p*2]+=b[p]*(mid-s+1);
d[p*2+1]+=b[p]*(e-mid);
// 修改当前子节点的值
b[p*2]+=b[p];
b[p*2+1]+=b[p];
// 将标记下传给子节点
b[p]=0;
// 清空当前节点的标记
}
if(l<=mid)add(l,r,c,s,mid,p*2);
// 处理左子节点
if(r>mid)add(l,r,c,mid+1,e,p*2+1);
// 处理右子节点
d[p]=d[p*2]+d[p*2+1];
// 修改当前节点的值
}
int find_change(int l,int r,int s,int e,int p){//区间查询（修改版）
// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
if(l<=s&&e<=r){
return d[p];
}// 当前区间为询问区间的子集时直接返回当前区间的和
int mid=s+((e-s)>>1);
if(b[p]!=0){
d[p*2]+=b[p]*(mid-s+1);
d[p*2+1]+=b[p]*(e-mid);
// 修改当前节点
b[p*2]+=b[p];
b[p*2+1]+=b[p];
// 将标记下传给子节点
b[p]=0;
// 清空当前节点的标记
}
int sum=0;
if(l<=mid)sum+=find_change(l,r,s,mid,p*2);
// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
if(r>mid)sum+=find_change(l,r,mid+1,e,p*2+1);
// 如果右儿子代表的区间[mid+1,r]与询问区间有交集，则递归查询右儿子
return sum;
}
signed main(){
//cin>>n>>m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
//cin>>a[i];
scanf("%lld",&a[i]);
}
build(1,n,1);
for(int i=1;i<=m;i++){
//cin>>op;
scanf("%lld",&op);
if(op==1){
//cin>>x>>y>>k;
scanf("%lld%lld%lld",&x,&y,&k);
add(x,y,k,1,n,1);
}else if(op==2){
//cin>>x>>y;
scanf("%lld%lld",&x,&y);
//cout<<find_change(x,y,1,n,1)<<endl;
printf("%lld\n",find_change(x,y,1,n,1));
}
}
return 0;
}