Lập trình C/C++

Thuật toán mảng cộng dồn (Full Code)

Posted on by Đỗ Thành
lập trình code chuyên nghiệp
13
Th1
View: 84

Thuật toán mảng cộng dồn là một kỹ thuật tối ưu trong lập trình, đặc biệt hữu ích trong việc tính tổng của các đoạn con của một mảng. Ý tưởng chính là xây dựng một mảng cộng dồn (prefix sum array), trong đó mỗi phần tử tại vị trí i lưu trữ tổng của tất cả các phần tử từ đầu mảng đến vị trí i. Điều này cho phép ta tính tổng của bất kỳ đoạn con nào trong thời gian O(1) sau khi mảng cộng dồn đã được chuẩn bị.

Ý tưởng:

1. Tạo một mảng cộng dồn prefix:

prefix[i] = prefix[i-1] + array[i] với prefix[0] = array[0]

          2. Tổng đoạn con từ chỉ số L đến R có thể tính bằng:

                sum[L, R] = prefix[R] – prefix[L – 1]

                Nếu L = 0, thì sum[L, R] = prefix[R]

          Lưu ý: Chỉ số của mảng (vector) trong C++ từ 0 đến n – 1

Độ phức tạp:

  • Chuẩn bị mảng cộng dồn: O(n)
  • Tính tổng đoạn con: O(1)
  • Tổng độ phức tạp: O(n) cho việc chuẩn bị, sau đó mỗi truy vấn chỉ mất O(1).

Kỹ thuật này rất hữu ích trong các bài toán có nhiều truy vấn tổng đoạn con, giúp giảm đáng kể thời gian tính toán.

Bài tập áp dụng:

1. Tính tổng đoạn con

Input: array = {1, 2, 3, 4, 5}; L = 1, R = 3

Output: Tổng đoạn [1, 3] là: 2 + 3 + 4 = 9

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Khởi tạo mảng array 
    vector<int> array = {1, 2, 3, 4, 5};
    int n = array.size(); // Lấy kích thước của mảng
    vector<int> prefix(n, 0); // Khởi tạo mảng prefix với kích thước n và giá trị ban đầu là 0

    // Tính mảng prefix, trong đó prefix[i] là tổng các phần tử từ array[0] đến array[i]
    prefix[0] = array[0]; // Phần tử đầu tiên của prefix bằng phần tử đầu tiên của array
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + array[i]; // Cộng dồn giá trị từ array vào prefix
    }

    // Định nghĩa đoạn con cần tính tổng
    int L = 1, R = 3; // Đoạn con từ vị trí L đến R (tính từ 0)

    // Tính tổng đoạn con từ L đến R
    int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0); // Nếu L > 0 thì trừ đi prefix[L - 1], ngược lại thì không trừ gì cả

    // In ra kết quả
    cout << "Tổng đoạn [" << L <<", "<< R << "]: " << sum << endl;

    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    // Khởi tạo mảng array
    int array[] = {1, 2, 3, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);// Lấy kích thước mảng
    int prefix[n]; // Khởi tạo mảng prefix với kích thước n

    // Tính mảng prefix, trong đó prefix[i] là tổng các phần tử từ array[0] đến array[i]
    prefix[0] = array[0]; 
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + array[i]; // Cộng dồn giá trị
    }

    // Định nghĩa đoạn con cần tính tổng
    int L = 1, R = 3; // Đoạn con từ vị trí L đến R (tính từ 0)

    // Tính tổng đoạn con từ L đến R
    int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0); // Nếu L > 0 thì trừ đi prefix[L - 1], ngược lại thì không trừ gì cả

    // In ra kết quả
    cout << "Tổng đoạn [" << L << ", " << R << "]:" << sum << endl;

    return 0;
}

2. Kiểm tra tổng đoạn con có lớn hơn một giá trị k

Input: array = {1, 2, 3, 4, 5} k = 10

Output: Số lượng đoạn con có tổng lớn hơn 10 là: 3

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {1, 2, 3, 4, 5}; // Khởi tạo mảng array
    int n = array.size(); // Lấy kích thước của mảng
    vector<int> prefix(n, 0); // Khởi tạo mảng prefix với kích thước n

    prefix[0] = array[0]; // Phần tử đầu tiên của prefix bằng phần tử đầu tiên của array
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + array[i]; // Tính tổng dồn cho mảng prefix
    }

    int k = 10, count = 0; // Giá trị k để so sánh và biến đếm count
    for (int L = 0; L < n; ++L) { // Duyệt qua các chỉ số bắt đầu của đoạn con
        for (int R = L; R < n; ++R) { // Duyệt qua các chỉ số kết thúc của đoạn con
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0); // Tính tổng đoạn con từ L đến R
            if (sum > k) count++; // Nếu tổng lớn hơn k thì tăng biến đếm count
        }
    }

    cout << "Số lượng đoạn có tổng lớn hơn " << k << " là: " << count << endl; // In kết quả

    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    // Khởi tạo mảng array
    int array[] = {1, 2, 3, 4, 5};
    int n = sizeof(array) / sizeof(array[0]); // Kích thước mảng
    int prefix[n]; // Khởi tạo mảng prefix với kích thước n

    prefix[0] = array[0]; // Phần tử đầu tiên của prefix 
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + array[i]; // Cộng dồn 
    }

    int k = 10, count = 0; // Giá trị k so sánh và biến đếm count
    for (int L = 0; L < n; ++L) { 
        for (int R = L; R < n; ++R) { 
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0); // Tính tổng đoạn con từ L đến R
            if (sum > k) count++; // Nếu tổng lớn hơn k thì tăng biến đếm count
        }
    }

    cout << "Số lượng đoạn có tổng lớn hơn " << k << " là: " << count << endl; // In kết quả

    return 0;
}

3. Tìm đoạn con có tổng lớn nhất

Input: array = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output: Tổng lớn nhất: 6 (đoạn con từ chỉ số 3 đến 6: [4, -1, 2, 1]

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<int> array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = array.size();
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int maxSum = INT_MIN;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            maxSum = max(maxSum, sum);
        }
    }
    cout << "Tổng lớn nhất: " << maxSum << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(array) / sizeof(array[0]); 
    int prefix[n]; // Khởi tạo mảng prefix với kích thước n

    prefix[0] = array[0]; 
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + array[i]; 
    }

    int maxSum = INT_MIN; // Khởi tạo biến maxSum với giá trị nhỏ nhất của kiểu int
    for (int L = 0; L < n; ++L) { 
        for (int R = L; R < n; ++R) { 
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0); // Tính tổng đoạn con từ L đến R
            maxSum = max(maxSum, sum); // Cập nhật maxSum nếu sum lớn hơn maxSum hiện tại
        }
    }

    cout << "Tổng lớn nhất: " << maxSum << endl; // In kết quả

    return 0;
}

4. Kiểm tra tổng đoạn con có bằng một giá trị

Input: array = {1, 2, 3, 4, 5} k = 10

Output: Đoạn con từ 1 đến 3 có tổng bằng 10 (đoạn con [2, 3, 4]).

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {1, 2, 3, 4, 5};
    int n = array.size();
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int k = 10;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum == k) cout << "Đoạn con từ " << L << " đến " << R << " có tổng bằng " << k << endl;
        }
    }
    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int k = 10;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum == k) cout << "Đoạn con từ " << L << " đến " << R << " có tổng bằng " << k << endl;
        }
    }
    return 0;
}

5. Tìm đoạn con có tổng nhỏ nhất

Input: array = {3, -4, 2, -1, -2, 6, -5}

Output: Tổng nhỏ nhất: -5 (đoạn con từ chỉ số 6 đến 6: [-5])

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    vector<int> array = {3, -4, 2, -1, -2, 6, -5};
    int n = array.size();
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int minSum = INT_MAX;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            minSum = min(minSum, sum);
        }
    }
    cout << "Tổng nhỏ nhất: " << minSum << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int array[] = {3, -4, 2, -1, -2, 6, -5};
    int n = sizeof(array) / sizeof(array[0]);
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int minSum = INT_MAX;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            minSum = min(minSum, sum);
        }
    }
    cout << "Tổng nhỏ nhất: " << minSum << endl;
    return 0;
}

6. Tìm đoạn con dài nhất có tổng nhỏ hơn k

Input: array = {1, 2, -3, 4, 5} k = 6

Output: Độ dài lớn nhất: 4 (đoạn con từ chỉ số 0 đến 3: [1, 2, -3, 4])

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {1, 2, -3, 4, 5};
    int n = array.size();
    int k = 6;
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int maxLength = 0;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum < k)
                maxLength = max(maxLength, R - L + 1);
        }
    }
    cout << "Độ dài lớn nhất: " << maxLength << endl;
    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    int array[] = {1, 2, -3, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);
    int k = 6;
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int maxLength = 0;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum < k)
                maxLength = max(maxLength, R - L + 1);
        }
    }
    cout << "Độ dài lớn nhất: " << maxLength << endl;
    return 0;
}

7. Đếm số đoạn con có tổng là 0

Input: array = {1, 2, -3, 4, 5} k = 6

Output: Độ dài lớn nhất: 4 (đoạn con từ chỉ số 0 đến 3: [1, 2, -3, 4])

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> array = {1, 2, -3, 3, -3};
    int n = array.size();
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // Tổng = 0 trước mảng
    int prefixSum = 0, count = 0;

    for (int i = 0; i < n; ++i) {
        prefixSum += array[i];
        if (prefixCount.count(prefixSum))
            count += prefixCount[prefixSum];
        prefixCount[prefixSum]++;
    }
    cout << "Số đoạn con có tổng = 0: " << count << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int array[] = {1, 2, -3, 3, -3};
    int n = sizeof(array) / sizeof(array[0]);
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // Tổng = 0 trước mảng
    int prefixSum = 0, count = 0;

    for (int i = 0; i < n; ++i) {
        prefixSum += array[i];
        if (prefixCount.count(prefixSum))
            count += prefixCount[prefixSum];
        prefixCount[prefixSum]++;
    }
    cout << "Số đoạn con có tổng = 0: " << count << endl;
    return 0;
}

9. Kiểm tra đoạn con có tổng chia hết cho k

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {2, 7, 6, 1, 4, 5};
    int n = array.size(), k = 5;
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum % k == 0) {
                cout << "Đoạn từ " << L << " đến " << R << " có tổng chia hết cho " << k << endl;
            }
        }
    }
    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    int array[] = {2, 7, 6, 1, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);
    int k = 5;
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum % k == 0) {
                cout << "Đoạn từ " << L << " đến " << R << " có tổng chia hết cho " << k << endl;
            }
        }
    }
    return 0;
}

10. Tìm đoạn con có tổng chẵn dài nhất

Input: array = {2, 3, 1, 6, 4, 5}

Output: Độ dài lớn nhất của đoạn con có tổng chẵn là: 5

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {2, 3, 1, 6, 4, 5};
    int n = array.size();
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int maxLength = 0;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum % 2 == 0)
                maxLength = max(maxLength, R - L + 1);
        }
    }
    cout << "Độ dài lớn nhất của đoạn con có tổng chẵn là: " << maxLength << endl;
    return 0;
}

11. Tính tổng bình phương các phần tử trong một đoạn con

Input: array = {1, 2, 3, 4} L = 1 R = 3

Output: Tổng bình phương từ 1 đến 3 là: 22 + 32 + 42 = 4 + 9 + 16 = 29

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {1, 2, 3, 4};
    int n = array.size();
    vector<int> prefixSquare(n, 0);

    prefixSquare[0] = array[0] * array[0];
    for (int i = 1; i < n; ++i)
        prefixSquare[i] = prefixSquare[i - 1] + array[i] * array[i];

    int L = 1, R = 3;
    int sumSquare = prefixSquare[R] - (L > 0 ? prefixSquare[L - 1] : 0);
    cout << "Tổng bình phương từ " << L << " đến " << R << " là: " << sumSquare << endl;
    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    int array[] = {1, 2, 3, 4};
    int n = sizeof(array) / sizeof(array[0]);
    int prefixSquare[n];

    prefixSquare[0] = array[0] * array[0];
    for (int i = 1; i < n; ++i)
        prefixSquare[i] = prefixSquare[i - 1] + array[i] * array[i];

    int L = 1, R = 3;
    int sumSquare = prefixSquare[R] - (L > 0 ? prefixSquare[L - 1] : 0);
    cout << "Tổng bình phương từ " << L << " đến " << R << " là: " << sumSquare << endl;
    return 0;
}

12. Tính tổng các đoạn con lẻ

Input: array = {1, 2, 3, 4}

Output: Tổng các đoạn con có tổng lẻ là: 35

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> array = {1, 2, 3, 4};
    int n = array.size();
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int totalOddSum = 0;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum % 2 != 0) totalOddSum += sum;
        }
    }
    cout << "Tổng các đoạn con có tổng lẻ là: " << totalOddSum << endl;
    return 0;
}

Mảng:

#include <iostream>
using namespace std;

int main() {
    int array[] = {1, 2, 3, 4};
    int n = sizeof(array) / sizeof(array[0]);
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    int totalOddSum = 0;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (sum % 2 != 0) totalOddSum += sum;
        }
    }
    cout << "Tổng các đoạn con có tổng lẻ là: " << totalOddSum << endl;
    return 0;
}

13. Đếm số đoạn con có tổng là số nguyên tố

Input: array = {2, 3, 4, 6, 7}

Output: Số đoạn con có tổng là số nguyên tố: 6

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); ++i)
        if (num % i == 0) return false;
    return true;
}

int main() {
    vector<int> array = {2, 3, 4, 6, 7};
    int n = array.size(), count = 0;
    vector<int> prefix(n, 0);

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (isPrime(sum)) count++;
        }
    }
    cout << "Số đoạn con có tổng là số nguyên tố: " << count << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); ++i)
        if (num % i == 0) return false;
    return true;
}

int main() {
    int array[] = {2, 3, 4, 6, 7};
    int n = sizeof(array) / sizeof(array[0]);
    int count = 0;
    int prefix[n];

    prefix[0] = array[0];
    for (int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + array[i];

    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            int sum = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
            if (isPrime(sum)) count++;
        }
    }
    cout << "Số đoạn con có tổng là số nguyên tố: " << count << endl;
    return 0;
}

14. Đếm số đoạn con có tổng chia hết cho k

Input: array = {1, 2, 3, 4, 5} k = 3

Output: Số đoạn con có tổng chia hết cho 3: 4

Code tham khảo:

Vector:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> array = {1, 2, 3, 4, 5};
    int n = array.size(), k = 3, count = 0;
    unordered_map<int, int> modCount;
    modCount[0] = 1;

    int prefixSum = 0;
    for (int i = 0; i < n; ++i) {
        prefixSum += array[i];
        int mod = (prefixSum % k + k) % k;
        if (modCount.count(mod)) count += modCount[mod];
        modCount[mod]++;
    }
    cout << "Số đoạn con có tổng chia hết cho " << k << ": " << count << endl;
    return 0;
}

Mảng:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int n = sizeof(array) / sizeof(array[0]);
    int k = 3, count = 0;
    unordered_map<int, int> modCount;
    modCount[0] = 1;

    int prefixSum = 0;
    for (int i = 0; i < n; ++i) {
        prefixSum += array[i];
        int mod = (prefixSum % k + k) % k;
        if (modCount.count(mod)) count += modCount[mod];
        modCount[mod]++;
    }
    cout << "Số đoạn con có tổng chia hết cho " << k << ": " << count << endl;
    return 0;
}

Bài tập tham khảo 1

Bài 1. Đoạn con có tổng nhỏ nhất

Viết chương trình tìm đoạn con (subarray) có tổng nhỏ nhất trong mảng sử dụng mảng cộng dồn.

Bài 2. Tìm đoạn con có tổng chẵn dài nhất

Tìm độ dài lớn nhất của đoạn con có tổng chẵn từ một mảng số nguyên.

Bài 3. Kiểm tra tính chất đối xứng của tổng đoạn con

Cho một mảng số nguyên. Kiểm tra xem có tồn tại hai đoạn con bất kỳ có tổng bằng nhau và không giao nhau hay không.

Bài 4. Tìm đoạn con có tổng lớn nhất mà không vượt quá k

Nhập vào một số k. Tìm đoạn con trong mảng có tổng lớn nhất nhưng không vượt quá k.

Bài 5. Tính tổng bình phương của tất cả các đoạn con

Viết chương trình tính tổng bình phương của tất cả các đoạn con trong một mảng sử dụng mảng cộng dồn.

Bài 6. Đếm số đoạn con có tổng là bội của k

Cho số nguyên k. Đếm số đoạn con có tổng chia hết cho k.

Bài 7: Tìm đoạn con có tổng gần x nhất

Nhập một số x. Tìm đoạn con có tổng gần với x nhất.

Bài 8. Đếm số đoạn con có tổng trong khoảng [L,R]

Cho hai số L và R. Đếm số đoạn con có tổng nằm trong khoảng [L,R].

Bài 9. Tính tổng các phần tử của đoạn con từ chỉ số L đến R nhiều lần

Cho nhiều cặp chỉ số L,R. Với mỗi cặp, tính tổng các phần tử trong đoạn đó. Dữ liệu đầu vào cần tối ưu.

Bài 10. Tìm đoạn con có tổng lớn nhất với x lần cộng dồn Nhập số nguyên x. Tìm đoạn con trong mảng có tổng lớn nhất với việc chỉ sử dụng x lần phép cộng.

Code tham khảo chung:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <climits>
#include <cmath>

using namespace std;

// Bài 1: Đoạn con có tổng nhỏ nhất
int minSubarraySum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
    int minSum = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            minSum = min(minSum, prefix[j] - prefix[i]);
        }
    }
    return minSum;
}

// Bài 2: Tìm đoạn con có tổng chẵn dài nhất
int longestEvenSumSubarray(const vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> pos;
    pos[0] = -1;
    int sum = 0, maxLength = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        int mod = sum % 2;
        if (pos.find(mod) != pos.end()) {
            maxLength = max(maxLength, i - pos[mod]);
        } else {
            pos[mod] = i;
        }
    }
    return maxLength;
}

// Bài 3: Kiểm tra tính chất đối xứng của tổng đoạn con
bool hasEqualSumSubarrays(const vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> sumFreq;
    sumFreq[0] = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sumFreq[sum] > 0) return true;
        sumFreq[sum]++;
    }
    return false;
}

// Bài 4: Tìm đoạn con có tổng lớn nhất mà không vượt quá k
int maxSubarraySumNoMoreThanK(const vector<int>& arr, int k) {
    int n = arr.size();
    set<int> prefixSums;
    prefixSums.insert(0);
    int sum = 0, maxSum = INT_MIN;
    for (int num : arr) {
        sum += num;
        auto it = prefixSums.lower_bound(sum - k);
        if (it != prefixSums.end()) maxSum = max(maxSum, sum - *it);
        prefixSums.insert(sum);
    }
    return maxSum;
}

// Bài 5: Tính tổng bình phương của tất cả các đoạn con
long long sumOfSquaresOfSubarrays(const vector<int>& arr) {
    int n = arr.size();
    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            result += sum * sum;
        }
    }
    return result;
}

// Bài 6: Đếm số đoạn con có tổng là bội của k
int countSubarraysDivisibleByK(const vector<int>& arr, int k) {
    unordered_map<int, int> modCount;
    modCount[0] = 1;
    int sum = 0, count = 0;
    for (int num : arr) {
        sum += num;
        int mod = ((sum % k) + k) % k;
        count += modCount[mod];
        modCount[mod]++;
    }
    return count;
}

// Bài 7: Tìm đoạn con có tổng gần x nhất
int closestSubarraySum(const vector<int>& arr, int x) {
    int n = arr.size();
    set<int> prefixSums;
    prefixSums.insert(0);
    int sum = 0, closest = INT_MAX;
    for (int num : arr) {
        sum += num;
        auto it = prefixSums.lower_bound(sum - x);
        if (it != prefixSums.end()) closest = min(closest, abs(sum - *it - x));
        if (it != prefixSums.begin()) {
            --it;
            closest = min(closest, abs(sum - *it - x));
        }
        prefixSums.insert(sum);
    }
    return closest;
}

// Bài 8: Đếm số đoạn con có tổng trong khoảng [L, R]
int countSubarraysInRange(const vector<int>& arr, int L, int R) {
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum >= L && sum <= R) count++;
        }
    }
    return count;
}

// Bài 9: Tính tổng các phần tử của đoạn con từ chỉ số L đến R
vector<int> rangeSumQueries(const vector<int>& arr, const vector<pair<int, int>>& queries) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0), result;
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
    for (auto [L, R] : queries) result.push_back(prefix[R + 1] - prefix[L]);
    return result;
}

// Bài 10: Tìm đoạn con có tổng lớn nhất với x lần cộng dồn
int maxSubarraySumWithXOps(const vector<int>& arr, int x) {
    int n = arr.size(), maxSum = INT_MIN;
    for (int i = 0; i <= n - x; i++) {
        int sum = 0;
        for (int j = 0; j < x; j++) sum += arr[i + j];
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

Bài tập tham khảo 2

  1. Tìm đoạn con có tổng lớn nhất với độ dài cố định:
    1. Input: Một mảng số nguyên và một giá trị d (độ dài cố định).
    1. Output: Tổng lớn nhất của đoạn con có độ dài d.
  2. Tìm đoạn con có tổng nhỏ nhất với độ dài cố định:
    1. Input: Một mảng số nguyên và một giá trị d (độ dài cố định).
    1. Output: Tổng nhỏ nhất của đoạn con có độ dài d.
  3. Tìm đoạn con có tổng lớn nhất với độ dài không vượt quá d:
    1. Input: Một mảng số nguyên và một giá trị d (độ dài tối đa).
    1. Output: Tổng lớn nhất của đoạn con có độ dài không vượt quá d.
  4. Tìm đoạn con có tổng nhỏ nhất với độ dài không vượt quá d:
    1. Input: Một mảng số nguyên và một giá trị d (độ dài tối đa).
    1. Output: Tổng nhỏ nhất của đoạn con có độ dài không vượt quá d.
  5. Đếm số đoạn con có tổng nằm trong khoảng [a, b]:
    1. Input: Một mảng số nguyên và hai giá trị a, b.
    1. Output: Số lượng đoạn con có tổng nằm trong khoảng [a, b].
  6. Tìm đoạn con có tổng lớn nhất với tổng các phần tử chẵn:
    1. Input: Một mảng số nguyên.
    1. Output: Tổng lớn nhất của đoạn con mà tổng các phần tử trong đoạn con đó là số chẵn.
  7. Tìm đoạn con có tổng nhỏ nhất với tổng các phần tử lẻ:
    1. Input: Một mảng số nguyên.
    1. Output: Tổng nhỏ nhất của đoạn con mà tổng các phần tử trong đoạn con đó là số lẻ.
  8. Tìm đoạn con có tổng lớn nhất với tổng các phần tử là bội của k:
    1. Input: Một mảng số nguyên và một giá trị k.
    1. Output: Tổng lớn nhất của đoạn con mà tổng các phần tử trong đoạn con đó là bội của k.
  9. Tìm đoạn con có tổng nhỏ nhất với tổng các phần tử là bội của k:
    1. Input: Một mảng số nguyên và một giá trị k.
    1. Output: Tổng nhỏ nhất của đoạn con mà tổng các phần tử trong đoạn con đó là bội của k.
  10. Tìm đoạn con có tổng lớn nhất với tổng các phần tử là số nguyên tố:
    1. Input: Một mảng số nguyên.
    1. Output: Tổng lớn nhất của đoạn con mà tổng các phần tử trong đoạn con đó là số nguyên tố.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <climits>
#include <cmath>

using namespace std;

// Bài 1: Đoạn con có tổng nhỏ nhất
int minSubarraySum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
    int minSum = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            minSum = min(minSum, prefix[j] - prefix[i]);
        }
    }
    return minSum;
}

// Bài 2: Tìm đoạn con có tổng chẵn dài nhất
int longestEvenSumSubarray(const vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> pos;
    pos[0] = -1;
    int sum = 0, maxLength = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        int mod = sum % 2;
        if (pos.find(mod) != pos.end()) {
            maxLength = max(maxLength, i - pos[mod]);
        } else {
            pos[mod] = i;
        }
    }
    return maxLength;
}

// Bài 3: Kiểm tra tính chất đối xứng của tổng đoạn con
bool hasEqualSumSubarrays(const vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> sumFreq;
    sumFreq[0] = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sumFreq[sum] > 0) return true;
        sumFreq[sum]++;
    }
    return false;
}

// Bài 4: Tìm đoạn con có tổng lớn nhất mà không vượt quá k
int maxSubarraySumNoMoreThanK(const vector<int>& arr, int k) {
    int n = arr.size();
    set<int> prefixSums;
    prefixSums.insert(0);
    int sum = 0, maxSum = INT_MIN;
    for (int num : arr) {
        sum += num;
        auto it = prefixSums.lower_bound(sum - k);
        if (it != prefixSums.end()) maxSum = max(maxSum, sum - *it);
        prefixSums.insert(sum);
    }
    return maxSum;
}

// Bài 5: Tính tổng bình phương của tất cả các đoạn con
long long sumOfSquaresOfSubarrays(const vector<int>& arr) {
    int n = arr.size();
    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            result += sum * sum;
        }
    }
    return result;
}

// Bài 6: Đếm số đoạn con có tổng là bội của k
int countSubarraysDivisibleByK(const vector<int>& arr, int k) {
    unordered_map<int, int> modCount;
    modCount[0] = 1;
    int sum = 0, count = 0;
    for (int num : arr) {
        sum += num;
        int mod = ((sum % k) + k) % k;
        count += modCount[mod];
        modCount[mod]++;
    }
    return count;
}

// Bài 7: Tìm đoạn con có tổng gần x nhất
int closestSubarraySum(const vector<int>& arr, int x) {
    int n = arr.size();
    set<int> prefixSums;
    prefixSums.insert(0);
    int sum = 0, closest = INT_MAX;
    for (int num : arr) {
        sum += num;
        auto it = prefixSums.lower_bound(sum - x);
        if (it != prefixSums.end()) closest = min(closest, abs(sum - *it - x));
        if (it != prefixSums.begin()) {
            --it;
            closest = min(closest, abs(sum - *it - x));
        }
        prefixSums.insert(sum);
    }
    return closest;
}

// Bài 8: Đếm số đoạn con có tổng trong khoảng [L, R]
int countSubarraysInRange(const vector<int>& arr, int L, int R) {
    int count = 0, n = arr.size();
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum >= L && sum <= R) count++;
        }
    }
    return count;
}

// Bài 9: Tổng đoạn con có độ dài cố định
int maxFixedLengthSubarraySum(const vector<int>& arr, int d) {
    int n = arr.size();
    int sum = 0, maxSum = INT_MIN;
    for (int i = 0; i < d; i++) sum += arr[i];
    maxSum = sum;
    for (int i = d; i < n; i++) {
        sum += arr[i] - arr[i - d];
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

// Bài 10: Tổng đoạn con là số nguyên tố
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int maxPrimeSumSubarray(const vector<int>& arr) {
    int n = arr.size(), maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (isPrime(sum)) maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

CHÚC CÁC BẠN HỌC TỐT!

Đỗ Thành