Mảng cộng dồn (tăng, giảm trên đoạn) mảng 1 chiều trong C++

• • 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;
}