【模板】线段树 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;
const int MAXN=1e5+9;
using i64 = long long;
struct tree
{
int l; // 左儿子
int r; // 右儿子
i64 add;// 懒标记
i64 value;// 维护的区间内的值
};
i64 arr[MAXN];
tree t[MAXN*4+2];// 记住这里要全初始化为零
void create(int x,int l,int r)
{
t[x].l=l,t[x].r=r;
if(l==r)
{
t[x].value=arr[l];// 注意这里value是递归返回的
return ;
}
int mid =t[x].l+(t[x].r-t[x].l)/2;
create(x*2,l,mid);
create(x*2+1,mid+1,r);
t[x].value=t[x*2].value+t[x*2+1].value;//递归返回整个区间维护的值
}
void spread(int p)
{
if(t[p].add!=0)//存在懒标记,那么就把懒标记往下面传递
{
t[p*2].value+=(t[p*2].r-t[p*2].l+1)*t[p].add;
t[p*2+1].value+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add;
t[p*2].add+=t[p].add;// 乘二啊我擦！！！
t[p*2+1].add+=t[p].add;
// 标记下移，但是只移动一次,能节省时间，待需要的时候再往下移动
t[p].add=0;
}
}
void change(int p,int x,int y,int z)//递归返回查询结果
{
if(x<=t[p].l&&t[p].r<=y)// 注意这个范围，这个区间要完整包含于我ask的区间
{
t[p].value+=(t[p].r-t[p].l+1)*z;
t[p].add+=z;//代表如果要查询儿子,就必须先把懒标记下移,而这里不下移动，因为本次查询不需要再向下调整了，可以把多次调整转化成一次调整，从而提高调整效率
return ;
}
spread(p);//下移懒标记,这里非常关键
int mid=(t[p].l+t[p].r)/2;
if(x<=mid)
{
change(p*2,x,y,z);//change的时候x y 是选中的范围，这个是不能改的
}
if(y>mid)
{
change(p*2+1,x,y,z);
}
t[p].value=t[p*2].value+t[p*2+1].value;
}
i64 ask(int p,int x,int y)
{
if(x<=t[p].l&&y>=t[p].r)return t[p].value;
spread(p); //这里也要下传懒标记，千万别忘了，如果是查询或者修改子数组，首先要下放懒标记
i64 ans=0;
int mid =(t[p].l+t[p].r)/2;
if(x<=mid)ans+=ask(p*2,x,y);//同理，ask 的时候也不能改！
if(y>mid) ans+=ask(p*2+1,x,y);
return ans;
}
int main()
{
int n,m;
std::cin>>n>>m;
for(int i=1;i<=n;i++)
{
std::cin>>arr[i];
}
create(1,1,n);
for(int i=1;i<=m;i++)
{
int t;
std::cin>>t;
if(t==1)
{
int a,b,c;
std::cin>>a>>b>>c;
change(1,a,b,c);
}
else
{
int x,y;
std::cin>>x>>y;
i64 ans= ask(1,x,y);
cout<<ans<<'\n';
}
}
return 0;
}