-
- Sử dụng mảng cộng dồn để tính tăng, giảm một lượng V đơn vị trong đoạn từ Left đến Right của mảng 1 chiều a[n].
- Ví dụ:

- Ta thực hiện như sau : tăng từ đoạn a[0] đến a[2] tăng lên 2 đơn vị
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
2 |
|
|
-2 |
|
|
|
|
- Do chỉ tăng đoạn a[0] ⇒ a[2] lên 2 đơn vị nên chỗ a[3] ta đánh dấu là -2. Nếu vị trí a[3] ta không đánh dấu là -2 thì nó sẽ tăng hết lên 2 đơn vị từ a[0] ⇒ a[7].
- Tương tự : đoạn a[1] đến a[2] giảm 1 đơn vị
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
2 |
|
|
-2 |
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
- Đoạn a[2] đến a[4] tăng lên 5 đơn vị
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
2 |
|
|
-2 |
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
- Đoạn a[5] đến a[7] tăng lên 3 đơn vị
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
|
2 |
|
|
-2 |
|
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
|
|
|
|
|
|
|
3 |
|
|
-3 |
- Đoạn a[1] đến a[6] tăng lên 4 đơn vị
-
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
|
2 |
|
|
-2 |
|
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
|
|
|
|
|
|
|
3 |
|
|
-3 |
|
|
4 |
|
|
|
|
|
-4 |
|
- Tính tổng từng phần tử thay đổi từ a[0] ⇒ a[7]
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
|
2 |
|
|
-2 |
|
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
|
|
|
|
|
|
|
3 |
|
|
-3 |
|
|
4 |
|
|
|
|
|
-4 |
|
Tổng |
2 |
-1 +4 =3 |
5 |
-2+1 = -1 |
0 |
-5+3 = -2 |
0 |
-4 |
|
- Chỗ a[8] = -3 ta không cần quan tâm vì mảng chúng ta chỉ có 7 phần tử.
- Xây dựng mảng cộng dồn prefix sum/f
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
2 |
|
|
-2 |
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
|
-4 |
Tổng |
2 |
3 |
5 |
-1 |
0 |
-2 |
0 |
-4 |
prefix sum/f |
2 |
5 |
10 |
9 |
9 |
7 |
7 |
3 |
- Kết quả cuối cùng sau khi tăng giảm V đơn vị:
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
11 |
|
2 |
|
|
-2 |
|
|
|
|
|
|
-1 |
|
1 |
|
|
|
|
|
|
|
5 |
|
|
-5 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
|
-4 |
g[i] |
2 |
3 |
5 |
-1 |
0 |
-2 |
0 |
-4 |
f[i]=f[i-1]+g[i] |
2 |
5 |
10 |
9 |
9 |
7 |
7 |
3 |
s=a[n]+f[i] |
6 |
2 |
15 |
12 |
16 |
13 |
16 |
14 |

- Code C++:
#include <bits/stdc++.h>
using namespace std;
int n, t, a[1005], f[1005], g[1005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("input.inp","r",stdin);
freopen("output.out","w",stdout);
cin>>n;
for (int i=0; i<n; i++)
cin>>a[i];
cin>>t;
while(t--)
{
int l, r , v;
cin>>l>>r>>v;
g[l] += v;
g[r+1] -= v;
}
for (int i=0; i<n; i++)
f[i] = f[i-1]+g[i];
for (int i=0; i<n; i++)
a[i] += f[i];
for (int i=0; i<n; i++)
cout<<a[i]<< " ";
return 0;
}

Số lượt xem: 759