# Prefix Sum - Tối ưu bộ nhớ
## Kiến thức cần biết
- **Prefix Sum** cơ bản
- Tăng các phần tử từ đoạn $l$ đến $r$ trong $O(1)$ dùng **Prefix Sum**
- **Unordered_map** hoặc **Map**
- **Vector** hoặc **Mảng Tĩnh**
## Khái quát
### Bài toán:
Cho $n$ số nguyên dương $a[i]$ và $t$ truy vấn, mỗi truy vấn cho ba số nguyên $l, r, x$, cần tăng các phần tử trong đoạn $l$ đến đoạn $r$ lên $x$ đơn vị. In ra $n$ số nguyên dương $a[i]$ sau $t$ truy vấn?
- $1 <= l <= r <= n <= 10^5$
- $1 <= t <= 10^5$
- $1 <= x, a[i] <= 10^9$
### Lời giải:
Ta tạo một mảng $S$ gồm $n$ phần tử, với mỗi truy vấn, ta tăng $S[l]$ lên x đơn vị và giảm $S[r + 1]$ đi x đơn vị.

Sau các truy vấn, ta chạy $i$ ($1 <= i <= n$) và đặt $S[i] += S[i - 1]$.

Từ đây muốn suy ra mảng $a$, với mỗi phần tử thứ $i$ thì giá trị của nó sau khi cập nhật là $a[i] + S[i]$.

#Code mẫu, có thể ko ac xd
n, t = map(int, input().split())
a = [0] + list(map(int, input().split()))
S = [0] * (n + 2)
for _ in range(t):
    l, r, x = map(int, input().split())
    S[l] += x
    S[r + 1] -= x
for i in range(1, n + 1): S[i] += S[i - 1]
for i in range(1, n + 1): print(a[i] + S[i], end = " ")

## Tầng nhà (THTB Sơn Trà 2022)
### Đề bài: https://ibb.co/RDm8x1C
### Lời giải:
#### Subtask 1 & 2 (1 <= a[i] <= 10^6):
Ta tạo ra mảng $S$ gồm $10^6$ phần tử, với $S[i]$ là số lượng toà nhà cô độc của ngày thứ $i$.

Xét từng toà nhà thứ $i$, kiểm tra xem nó có thể cô độc vào một ngày nào đó không ($a[i - 1] < a[i] > a[i + 1]$).

Nếu có, ta tính toán ra $l$ (là ngày đầu tiên toà nhà đó cô độc) và $r$ (là ngày cuối cùng toà nhà đó còn cô độc) của toà nhà đó.

**Công thức:**
- $l = max(a[i - 1], a[i + 1]) + 1$
- $r = a[i]$

Với mỗi $l$ và $r$ của toà nhà thứ $i$, ta tăng $S[l]$ lên $1$ và $S[r + 1]$ xuống $1$, áp dụng bài toán mở đầu.

Sau khi xét tất cả các toà nhà, ta chạy $i$ ($1 <= i <= n$) và đặt $S[i] += S[i - 1]$.

Kết quả sẽ là số lớn nhất của các $S[i]$

//Không copy code
ll n, a[100005], mx = 0, kq, S[1000006]; //Mảng S là lưu các ngày
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++){
        if (a[i - 1] < a[i] && a[i] > a[i + 1]){ //Nếu toà thứ i có thể đơn độc
            S[max(a[i - 1], a[i + 1]) + 1] += 1;
            S[a[i] + 1] -= 1;
            //Áp dụng bài toán mở đầu
        }
    }
    for (int i = 1; i <= 1e6; i++) S[i] += S[i - 1]; //Áp dụng bài toán mở đầu
    for (int i = 0; i <= 1e6; i++) mx = max(mx, S[i]); //Tìm max của các ngày
    cout << mx;
}

#### Subtask 3 (1 <= a[i] <= 10^18):
**Nhận xét:** Không cần lưu hết các ngày của mảng $S$, chỉ cần lưu các ngày then chốt.

Vậy các ngày then chốt là những ngày nào??? Ở code cho **Subtask 1 & 2**, cụ thể là **2 cái if đầu và cái for thứ 2**, ta chỉ cập nhật các ngày của mảng $S$ có dạng $a[i] + 1$, là ngày mà toà thứ $i$ chìm.

Tại sao chỉ lưu các ngày có dạng $a[i]+1$, vì các ngày đó sẽ có thể có sự kiện đặc biệt như số lượng toà cô độc tăng lên hay giảm xuống.

Ví dụ:
S[max(a[i - 1], a[i + 1]) + 1] += 1; thì có dạng S[a[i] + 1] += 1;
S[a[n] + 1] -= 1; thì có dạng S[a[i] + 1] -= 1;
S[a[2] + 1] += 1; thì có dạng S[a[i] + 1] += 1;

Từ đó ta chỉ cần lưu các ngày $a[i] + 1$ ở trong mảng $S$ ($1 <= i <= n$).

Dùng **unordered_map** (có thể dùng **map** nhưng sẽ chậm hơn)!

Tạo một **vector** $al$ (viết tắt của $all$) là các ngày then chốt của mình.

//Không copy code
ll n, a[100005], mx = 0;
unordered_map <ll, ll> S; //Tạo mảng S dùng unordered_map thay cho mảng tĩnh
vector <ll> al; //Vector lưu các ngày then chốt
unordered_map <ll, bool> check; //Kiểm tra xem ngày đó đã được lưu chưa
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (!check[a[i] + 1]){ //Kiểm tra xem ngày a[i] + 1 đã lưu chưa
            al.push_back(a[i] + 1);
            check[a[i] + 1] = true;
        }
    }
    for (int i = 1; i <= n; i++){
        if (a[i - 1] < a[i] && a[i] > a[i + 1]){ //Nếu toà thứ i có thể đơn độc
            S[max(a[i - 1], a[i + 1]) + 1] += 1;
            S[a[i] + 1] -= 1;
            //Áp dụng bài toán mở đầu
        }
    }
    sort(al.begin(), al.end()); //Sắp xếp lại, chuẩn bị để Prefix Sum
    for (int i = 1; i < al.size(); i++) S[al[i]] += S[al[i - 1]]; //Áp dụng bài toán mở đầu
    for (ll i : al) mx = max(mx, S[i]); //Tìm max của các ngày
    cout << mx;
}

## Vấn đề kĩ năng?

Khi chúng ta dùng **unordered_map**, hoặc **map**, thì sẽ ảnh hưởng tới tốc độ quyết của chương trình, vậy phải làm thế nào?

### 2051E: Best Price
Đề bài: https://codeforces.com/contest/2051/problem/E

const int N = 2e5 + 5, limit = 2e9;
int t, n, k, a[N + 1], b[N + 1];
vector<int> all;
map<int, bool> check;
void them(int x){
    if (!check[x]){
        check[x] = true;
        all.push_back(x);
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while (t--){
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        all.clear(); check.clear();
        them(1); them(limit);
        map<int, int> mua;
        map<int, int> niga;
        for (int i = 1; i <= n; i++){
            mua[1]++;
            mua[b[i] + 1]--;
            niga[a[i] + 1]++;
            niga[b[i] + 1]--;
 
            them(a[i]);
            them(b[i]);
            them(a[i] + 1);
            them(b[i] + 1);
        }
        sort(all.begin(), all.end());
        int vt = 0;
        ll mx = 0;
        for (int i = 1; i < all.size(); i++) mua[all[i]] += mua[all[i - 1]], niga[all[i]] += niga[all[i - 1]];
        for (int i = 0; i < all.size(); i++){
            ll tong = mua[all[i]] * (ll)all[i];
            int nx = niga[all[i]];
            if (nx <= k){
                if (tong > mx){
                    mx = tong;
                    vt = all[i];
                }
            }
        }
        cout << mx << "\n";
    }
}

Cách trên không sai, nhưng mà quá lạm dụng cấu trúc dữ liệu gây quá thời gian. Giải pháp là sẽ dùng **vector**. Hãy xem code dưới đây

const int N = 2e5 + 5, limit = 2e9;
int t, n, k, a[N + 1], b[N + 1];
vector<int> all;
map<int, bool> check;
vector<wtf> query1, query2;
void them(int x){
    if (!check[x]){
        check[x] = true;
        all.push_back(x);
    }
}
void muadi(int x, int val){ query1.push_back({x, val}); }
void danhgia(int x, int val){ query2.push_back({x, val}); }
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while (t--){
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        all.clear(); check.clear(); query1.clear(); query2.clear();
        them(1); them(limit);
        for (int i = 1; i <= n; i++){
            /*
            mua[1]++;
            mua[b[i] + 1]--;
            niga[a[i] + 1]++;
            niga[b[i] + 1]--;
            */
            muadi(1, 1);
            muadi(b[i] + 1, -1);
            danhgia(a[i] + 1, 1);
            danhgia(b[i] + 1, -1);
 
            them(a[i]);
            them(b[i]);
            them(a[i] + 1);
            them(b[i] + 1);
        }
        sort(all.begin(), all.end());
        sort(query1.begin(), query1.end());
        sort(query2.begin(), query2.end());
        vector<ll> mua(all.size(), 0), niga(all.size(), 0);
        for (int i = 0, j = 0; i < query1.size(); i++){
            while (all[j] != query1[i].fi) j++;
            mua[j] += query1[i].se;
        }
        for (int i = 0, j = 0; i < query2.size(); i++){
            while (all[j] != query2[i].fi) j++;
            niga[j] += query2[i].se;
        }
        for (int i = 1; i < all.size(); i++) mua[i] += mua[i - 1], niga[i] += niga[i - 1];
        ll mx = 0;
        for (int i = 0; i < all.size(); i++){
            ll tong = mua[i] * (ll)all[i];
            int nx = niga[i];
            if (nx <= k) mx = max(mx, tong);
        }
        cout << mx << "\n";
    }
}

Thao tác cập nhật trên đoạn , thì ta sẽ biến thành các truy vấn và hai con trỏ, chỉ cần dùng 1 map để biết được xem giá trị này đã được duyệt chưa.