# Mảng cộng dồn
---
**Tác giả : [Dương Nguyên Khánh](https://github.com/kduongnguyen07)**
###### tags:`Data Structure`,`Sum`,`Prefix sum`
# **Mở đầu**
Khi chúng ta cần sử dụng của các phần tử trong mảng thì 1 trong những cách hay được dùng để lưu trữ tổng là Prefix Sum hay còn được gọi là mảng cộng dồn
## Khái niệm
Cho một mảng A có n phần tử được đánh số từ 0 đến n−1, ta dựng mảng S(A) theo quy tắc sau: S[i+1] = S[i] + A[i]
<img src="https://i.imgur.com/lzBYJ89.gif">
## Cài đặt mảng cộng dồn

vector<int> buildPrefixSum(const vector<int>& a, int C = 0) {
    int n = (int)a.size();
    vector<int> prefixSum(n + 1);

    prefixSum[0] = C;

    for (int i = 0; i < n; i++)
        prefixSum[i + 1] = prefixSum[i] + a[i];

    return prefixSum;
}

## Ứng dụng của mảng cộng dồn
Mảng cộng dồn có một tính chất quan trọng: các phần tử được cộng lại chồng chất lên nhau một cách liên tiếp, vì thế, với mọi nửa khoảng [l,r) (0≤l<r≤n), ta chỉ cần tính Sr−Sl để tính tổng của các phần tử Al,Al+1,…,Ar−2,Ar−1. Việc trừ này cũng sẽ khử đi hằng số c của S, vì thế ta có thể dùng bất kỳ mảng S nào được sinh từ A để tính tổng.