acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

原题链接
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式
第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

题解
线段树模板

#include<bits/stdc++.h>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 2e5 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9;
struct Node{ 

int l,r;
ll v;
ll add;    //懒惰标记,保存当前节点以及子节点应该加上的值
}tr[N * 4];
int a[N];
void push_up(int u){ 

tr[u].v = tr[left(u)].v + (tr[left(u)].r - tr[left(u)].l + 1) * tr[left(u)].add
+ tr[right(u)].v + (tr[right(u)].r - tr[right(u)].l + 1) * tr[right(u)].add;
}
void push_down(int u){ 

if(tr[u].add){ 

tr[u].v += (tr[u].r - tr[u].l + 1) * tr[u].add;
tr[left(u)].add += tr[u].add;
tr[right(u)].add += tr[u].add;
tr[u].add = 0;
}
}
void build(int l,int r,int u){ 

if(l == r){ 

tr[u] = { 
l,r,a[l],0};
return;
}
else{ 

tr[u] = { 
l,r,0,0};
int mid = (l + r) >> 1;
build(l, mid, left(u));
build(mid + 1, r, right(u));
push_up(u);
}
}
ll query(int l,int r,int u){ 

push_down(u);
if(tr[u].l >= l && tr[u].r <= r){ 

return tr[u].v;
}
int mid = (tr[u].l + tr[u].r) >> 1;
ll sum = 0;
if(l <= mid)sum += query(l,r,left(u));
if(r > mid)sum += query(l,r,right(u));
return sum;
}
void modify(int l,int r,int x,int u){ 

if(tr[u].l >= l && tr[u].r <= r)tr[u].add += x;
else{ 

push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid)modify(l,r,x,left(u));
if(r > mid)modify(l,r,x,right(u));
push_up(u);     //修改了值就要push_up
}
}
void update(int x,int y,int u){ 

if(tr[u].l == x && tr[u].r == x)tr[u].v = y;
else{ 

push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid)update(x,y,left(u));
else update(x,y,right(u));
push_up(u);
}
}
int main(){ 

int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i ++){ 

cin>>a[i];
}
build(1,n,1);
char c;
int l,r,a;
for(int i = 0;i < m;i ++){ 

cin>>c>>l>>r;
if(c == 'Q'){ 

cout<<query(l,r,1)<<endl;
}else if(c == 'C'){ 

cin>>a;
modify(l,r,a,1);
}
}
return 0;
}