点击查看代码
// 对线段树的总结——by youyou2007 Aug.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#define int long long
#define REP(i, x, y) for(register int i = x; i < y; i++)
#define rep(i, x, y) for(register int i = x; i <= y; i++)
#define PER(i, x, y) for(register int i = x; i > y; i--)
#define per(i, x, y) for(register int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
const int N = 1E5 + 5;
int n, m;
int a[N];
int f[N * 4], tag[N * 4];//f数组即为模拟线段树数组,tag表示懒标记
void pushup(int k)//向上求和(合并)
{
f[k] = f[lc] + f[rc];
}
void sum(int l, int r, int k, int ttag)//更新懒标记与线段树的值
{
tag[k] += ttag;//懒标记+改变量
f[k] += ttag * (r - l + 1);//由于这是一个区间总和,区间中每个值都要+ttag,所以要加上这段区间的长度*ttag
}
void pushdown(int l, int r, int k)//下传标记操作
{
int mid = (l + r) / 2;
sum(l, mid, lc, tag[k]);//向左儿子传标记
sum(mid + 1, r, rc, tag[k]);//向右儿子传标记
tag[k] = 0;//注意这里要把这个位置上的懒标记清空
}
void build(int l, int r, int k)//建树过程
{
if(l == r)//如果搜到了叶子节点
{
f[k] = a[l];//则直接赋值
return;
}
int mid = (l + r) / 2;
build(l, mid, lc);//遍历左儿子
build(mid + 1, r, rc);//遍历右儿子
pushup(k);//递归完左右儿子后求和。
}
void modify(int l, int r, int ql, int qr, int k, int change)//修改
{
if(l == ql && r == qr)//如果刚好就要全改这个区间
{
tag[k] += change;//直接标记
f[k] += change * (r - l + 1);
return;
}
if(tag[k])//如果这个位置上有懒标记,则立刻下传4,避免冲突
{
pushdown(l, r, k);
}
int mid = (l + r) / 2;
if(qr <= mid)//①:如果修改的区间全在左儿子上
{
modify(l, mid, ql, qr, lc, change);
}
else if(ql >= mid + 1)//②:如果修改区间全在右儿子上
{
modify(mid + 1, r, ql, qr, rc, change);
}
else//③:如果两边都有,则都要搜索
{
modify(l, mid, ql, mid, lc, change);
modify(mid + 1, r, mid + 1, qr, rc, change);
}
pushup(k);//最后不要忘记上传标记
}
int query(int l, int r, int ql, int qr, int k)//求和
{
if(l == ql && r == qr)//如果刚好求和这个区间
{
return f[k];//直接返回这个区间的和
}
int mid = (l + r) / 2;
if(tag[k])
{
pushdown(l, r, k);
}
if(qr <= mid)//与修改相同,只是修改变成了求和
{
return query(l, mid, ql, qr, lc);
}
else if(ql >= mid + 1)
{
return query(mid + 1, r, ql, qr, rc);
}
else
{
return query(l, mid, ql, mid, lc) + query(mid + 1, r, mid + 1, qr, rc);
}
}
signed main()
{
scanf("%lld%lld", &n, &m);
rep(i, 1, n)
{
scanf("%lld", &a[i]);
}
build(1, n, 1);
while(m--)
{
int opt, x, y, kk;
scanf("%lld%lld%lld", &opt, &x, &y);
if(opt == 1)
{
scanf("%lld", &kk);
modify(1, n, x, y, 1, kk);
}
else
{
printf("%lld\n", query(1, n, x, y, 1));
}
}
}
code