区间 (interval)
时间限制：2秒 空间限制：32M
知识点：离散化
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
A
p
o
j
a
c
s
l
e
a
m
Apojacsleam
Apojacsleam 喜欢数组。
他现在有一个
n
n
n 个元素的数组
a
a
a ，而他要对
a
[
L
]
−
a
[
R
]
a[L]-a[R]
a[L]−a[R] 进行
M
M
M 次操作：
-
操作一：将
a
[
L
]
−
a
[
R
]
a[L]-a[R]
a[L]−a[R] 内的元素都加上
P
P
P
-
操作二：将
a
[
L
]
−
a
[
R
]
a[L]-a[R]
a[L]−a[R] 内的元素都减去
P
P
P
最后询问
a
[
l
]
−
a
[
r
]
a[l]-a[r]
a[l]−a[r] 内的元素之和？
请认真看题干及输入描述。
输入描述：
输入共
M
+
3
M+3
M+3 行：
第一行两个数，
n
n
n ，
M
M
M ，意义如“题目描述”
第二行
n
n
n 个数，描述数组。
第
3
−
M
+
2
3-M+2
3−M+2 行，共
M
M
M 行，每行四个数，
q
q
q ，
L
L
L ，
R
R
R ，
P
P
P ，若
q
q
q 为
1
1
1则表示执行操作
2
2
2 ，否则为执行操作
1
1
1
第
4
4
4 行，两个正整数
l
，
r
l，r
l，r
输出描述：
一个正整数，为
a
[
l
]
−
a
[
r
]
a[l]-a[r]
a[l]−a[r] 内的元素之和
示例1
输入：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5 5
1 2 3 6
0 2 5 5
0 2 5 8
1 4 9 6
2 7
输出：
23
说明：
1
≤
n
,
M
≤
1
,
000
,
000
1≤n,M≤1,000,000
1≤n,M≤1,000,000 ，所有输入数据都在
i
n
t
int
int 范围内
解题思路
本题是批量区间更新 + 单次区间求和的经典问题，数据规模达百万级，采用差分数组技巧实现线性复杂度求解，完美适配时间与空间约束。 核心原理：差分数组可以将区间加减操作的时间复杂度从
O
(
n
)
O(n)
O(n) 优化至
O
(
1
)
O(1)
O(1)，仅需最后一次前缀和计算，即可还原每个元素的最终增量，非常适合“多次更新、一次查询”的场景。 具体执行步骤：
O
(
n
+
m
)
O(n + m)
O(n+m)，空间复杂度为
O
(
n
)
O(n)
O(n)，在百万级数据下运行高效，且空间占用远低于32M限制。
总结
核心逻辑：利用差分数组将多次区间加减操作转化为两点更新，通过单次前缀和还原最终数组，同步计算目标区间和。 关键操作：差分数组的两点更新、操作类型的符号统一、前缀和计算与区间和累加同步完成。 效率保障：全程线性遍历，无嵌套循环，时间与空间复杂度均为最优，轻松应对百万级数据规模。
代码简要说明
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1000010;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll a[N], b[N];
void solve()
{
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= m; i++)
{
ll q, l, r, p;
cin >> q >> l >> r >> p;
if (q == 1) p = –p;
b[l] += p;
b[r + 1] -= p;
}
ll l, r;
cin >> l >> r;
ll ad = 0, rs = 0;
for (ll i = 1; i <= n; i++)
{
ad += b[i];
a[i] += ad;
if (i >= l && i <= r) rs += a[i];
}
cout << rs << '\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
