C++ STL Algorithms

⚙️ sort, lower_bound và upper_bound

Ba công cụ này thường đi cùng nhau: sắp xếp dữ liệu bằng sort, sau đó tìm biên bằng tìm kiếm nhị phân. Bài học giúp phân biệt chính xác “đầu tiên ≥ x”, “đầu tiên > x” và cách đếm số lần xuất hiện trong O(log n).

sortO(n log n)

lower_boundVị trí đầu tiên ≥ x

upper_boundVị trí đầu tiên > x

Count xupper − lower

Mục tiêu Đặt vấn đề sort Mô phỏng sort lower/upper Mô phỏng biên Comparator Ứng dụng Phân tích Code mẫu Giải thích code Lỗi thường gặp Quiz

🎯 Mục tiêu bài học

Cần hiểu

Cách dùng sort(first,last) trên phạm vi nửa mở.
Sắp xếp tăng, giảm và theo tiêu chí tùy chỉnh.
Ý nghĩa chính xác của lower_bound và upper_bound.
Điều kiện dữ liệu phải được sắp xếp.
Cách chuyển iterator thành chỉ số.

Cần làm được

Sắp xếp vector số và vector pair.
Tìm vị trí đầu tiên ≥ x và > x.
Kiểm tra x có tồn tại.
Đếm số lần xuất hiện của x.
Đếm số phần tử trong đoạn giá trị [L,R].

1. Đặt vấn đề

Bài toán mở đầu.
Cho mảng n số nguyên và q truy vấn. Mỗi truy vấn cho số x, cần:

Kiểm tra x có xuất hiện không.
Đếm số lần x xuất hiện.
Đếm số phần tử nhỏ hơn x.

1.1. Cách duyệt trực tiếp

Mỗi truy vấn duyệt toàn bộ mảng mất O(n). Với q truy vấn, tổng thời gian là O(nq).

1.2. Sắp xếp một lần, tìm kiếm nhiều lần

Nếu sắp xếp mảng trước:

Các phần tử bằng x nằm liên tiếp.
Có thể dùng tìm kiếm nhị phân để tìm biên trái và biên phải.
Mỗi truy vấn chỉ còn O(log n).

Sắp xếp O(n log n) + q truy vấn O(q log n)

Ý tưởng trung tâm: sort tạo tính đơn điệu; lower_bound và upper_bound khai thác tính đơn điệu đó.

2. Hàm sort

Tăng dần

sort(a.begin(), a.end());

Giảm dần

sort(a.begin(), a.end(), greater<int>());

Một đoạn

sort(a.begin()+L, a.begin()+R);

Sắp xếp chỉ số [L,R).

Phạm vi STL là nửa mở: iterator đầu được tính, iterator cuối không được tính.

2.1. Comparator tùy chỉnh

bool compare(const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }

    return a.name < b.name;
}

Comparator phải nghiêm ngặt. Không viết return a.score >= b.score;. Khi hai phần tử bằng nhau, comparator phải trả về false ở cả hai chiều.

3. Mô phỏng sort

Mảng Kiểu sắp xếp

L R

sort(a.begin(), a.end());
sort(a.begin(), a.end(), greater<int>());
sort(a.begin()+L, a.begin()+R);

Lưu ý: Mô phỏng chỉ minh họa kết quả trước/sau. Chuẩn C++ không bắt buộc std::sort phải dùng đúng một thuật toán nội bộ cụ thể.

4. lower_bound và upper_bound

lower_bound

vị trí đầu tiên có giá trị ≥ x

auto it = lower_bound(
    a.begin(),
    a.end(),
    x
);

upper_bound

vị trí đầu tiên có giá trị > x

auto it = upper_bound(
    a.begin(),
    a.end(),
    x
);

Mảng tăng	x	lower_bound	upper_bound	Số lần x xuất hiện
[1,2,2,2,5,7]	2	index 1	index 4	4−1=3
[1,2,2,2,5,7]	4	index 4	index 4	0
[1,2,2,2,5,7]	8	end()	end()	0

count(x) = upper_bound(x) − lower_bound(x)

Điều kiện bắt buộc: Phạm vi phải được sắp xếp theo cùng thứ tự so sánh mà hàm binary search đang dùng.

5. Mô phỏng lower_bound và upper_bound

Mảng đã sắp xếp x Chế độ

int left=0, right=n;
while (left < right) {
    int mid=(left+right)/2;
    if (a[mid] >= x) right=mid;
    if (a[mid] > x) right=mid;
    else left=mid+1;
}

6. sort với pair và comparator

Mặc định

pair được so sánh từ first, nếu bằng nhau mới so sánh second.

sort(items.begin(), items.end());

Tùy chỉnh

Sắp xếp điểm giảm dần; nếu hòa, mã tăng dần.

sort(items.begin(), items.end(),
    [](const auto& a, const auto& b) {
        if (a.second != b.second)
            return a.second > b.second;
        return a.first < b.first;
    }
);

6.1. Mô phỏng sắp xếp pair

Các pair dạng mã:điểm

7. Ứng dụng thường gặp

Kiểm tra tồn tại

auto it=lower_bound(a.begin(),a.end(),x);
bool exists=(it!=a.end() && *it==x);

Đếm nhỏ hơn x

int countLess=
    lower_bound(a.begin(),a.end(),x)
    - a.begin();

Đếm ≤ x

int countLE=
    upper_bound(a.begin(),a.end(),x)
    - a.begin();

Đếm trong [L,R]

int answer=
    upper_bound(a.begin(),a.end(),R)
    - lower_bound(a.begin(),a.end(),L);

Vị trí chèn giữ tăng

int pos=
    lower_bound(a.begin(),a.end(),x)
    - a.begin();

Số phần tử bằng x

auto [first,last]=equal_range(
    a.begin(),a.end(),x
);
int count=last-first;

8. Phân tích thuật toán

Thao tác	Độ phức tạp	Điều kiện / ghi chú
`sort` n phần tử	O(n log n)	Random-access iterator như vector, array, deque.
`lower_bound` trên vector tăng	O(log n)	Phạm vi đã sắp xếp.
`upper_bound` trên vector tăng	O(log n)	Phạm vi đã sắp xếp.
q truy vấn sau khi sort	O(n log n + q log n)	Hữu ích khi q lớn.
Chèn vào vector tại vị trí tìm được	O(n)	Tìm vị trí O(log n), nhưng dịch chuyển phần tử O(n).

Chi tiết quan trọng: Tìm vị trí bằng binary search là O(log n), nhưng chèn vào giữa vector vẫn O(n).

9. Code mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {7, 2, 9, 2, 5, 1};

    sort(a.begin(), a.end());

    for (int value : a) {
        cout << value << ' ';
    }

    cout << '\n';

    sort(
        a.begin(),
        a.end(),
        greater<int>()
    );

    for (int value : a) {
        cout << value << ' ';
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<long long> a(n);

    for (long long &value : a) {
        cin >> value;
    }

    sort(a.begin(), a.end());

    while (q--) {
        long long x;
        cin >> x;

        auto lower = lower_bound(
            a.begin(),
            a.end(),
            x
        );

        auto upper = upper_bound(
            a.begin(),
            a.end(),
            x
        );

        int firstPosition = lower - a.begin();
        int count = upper - lower;

        bool exists
            = lower != a.end()
            && *lower == x;

        cout << firstPosition
             << ' '
             << count
             << ' '
             << exists
             << '\n';
    }
}

long long countInClosedRange(
    const vector<long long>& a,
    long long leftValue,
    long long rightValue
) {
    auto first = lower_bound(
        a.begin(),
        a.end(),
        leftValue
    );

    auto afterLast = upper_bound(
        a.begin(),
        a.end(),
        rightValue
    );

    return afterLast - first;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int,int>> students = {
        {3, 8},
        {1, 9},
        {2, 8},
        {5, 10},
        {4, 9}
    };

    sort(
        students.begin(),
        students.end(),
        [](const pair<int,int>& a,
           const pair<int,int>& b) {
            if (a.second != b.second) {
                return a.second > b.second;
            }

            return a.first < b.first;
        }
    );

    for (auto [id, score] : students) {
        cout << id << ' '
             << score << '\n';
    }
}

from bisect import bisect_left, bisect_right

a = [7, 2, 9, 2, 5, 1]
a.sort()

x = 2

lower = bisect_left(a, x)
upper = bisect_right(a, x)

count_x = upper - lower
exists = lower < len(a) and a[lower] == x

print(lower, upper, count_x, exists)

10. Giải thích code

10.1. Vì sao sort dùng begin() và end()?

STL biểu diễn phạm vi bằng cặp iterator nửa mở [first,last). end() là vị trí ngay sau phần tử cuối.

10.2. Vì sao lower_bound có thể trả về end()?

Nếu mọi phần tử đều nhỏ hơn x, không có phần tử nào ≥ x. Vị trí chèn hợp lệ là cuối mảng, tức end().

10.3. Vì sao phải kiểm tra lower != end() trước khi *lower?

Không được dereference end(). Điều kiện ngắn mạch bảo đảm chỉ đọc *lower khi iterator hợp lệ.

10.4. Vì sao upper−lower bằng số lần x xuất hiện?

lower đứng trước phần tử x đầu tiên; upper đứng sau phần tử x cuối cùng. Khoảng nửa mở giữa hai iterator chứa đúng các phần tử bằng x.

10.5. Vì sao comparator không được dùng ≥?

sort yêu cầu strict weak ordering. Với hai phần tử bằng nhau, cả comp(a,b) và comp(b,a) phải false.

10.6. lower_bound trên mảng giảm dần dùng thế nào?

Phải truyền cùng comparator đã dùng để sắp xếp:

sort(a.begin(), a.end(), greater<int>());

auto it = lower_bound(
    a.begin(),
    a.end(),
    x,
    greater<int>()
);

10.7. Vì sao std::sort không dùng được trực tiếp với std::list?

std::sort cần random-access iterator. list chỉ có bidirectional iterator và cung cấp hàm thành viên list.sort().

11. Lỗi thường gặp

Dùng lower_bound hoặc upper_bound trên mảng chưa sắp xếp.
Nhầm lower_bound là phần tử đầu tiên > x.
Nhầm upper_bound là phần tử cuối cùng bằng x.
Dereference iterator bằng *it khi it == end().
Quên trừ a.begin() khi cần chỉ số.
Viết comparator bằng >= hoặc <=.
Sắp xếp giảm dần nhưng gọi lower_bound với comparator mặc định.
Nhầm đoạn STL [L,R) với đoạn đóng [L,R].
Cho rằng tìm vị trí O(log n) khiến thao tác insert vector cũng O(log n).
Dùng std::sort trực tiếp cho std::list.

12. Quiz và bài tập

Câu 1. lower_bound(a.begin(),a.end(),x) trả về gì?

Câu 2. upper_bound trả về gì?

Câu 3. Số phần tử bằng x được tính bằng?

Câu 4. Comparator nào đúng để sắp xếp giảm dần?

📘 Cơ bản

Sắp xếp tăng/giảm.
Tìm x có tồn tại.
Đếm số lần x xuất hiện.

📗 Trung bình

Đếm số phần tử nhỏ hơn x.
Đếm số phần tử trong [L,R].
Vị trí chèn giữ thứ tự tăng.

📙 Nâng cao

Sắp xếp struct nhiều tiêu chí.
Binary search trên vector pair.
Offline query sau khi sort.

🐉 HSG

Coordinate compression.
Meet-in-the-middle + bounds.
Đếm cặp bằng sort + binary search.