Sắp xếp nhanh (Quick Sort)

Thuật toán sắp xếp nhanh sử dụng phương pháp chia để trị, chọn một phần tử làm chốt (pivot) và phân vùng mảng thành hai phần.

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    
    int low = left - 1, high = right + 1;
    int pivot = nums[(left + right) / 2];
    
    while (low < high) {
        do low++; while (nums[low] < pivot);
        do high--; while (nums[high] > pivot);
        if (low < high) swap(nums[low], nums[high]);
    }
    
    quickSort(nums, left, high);
    quickSort(nums, high + 1, right);
}

Sắp xếp trộn (Merge Sort)

Thuật toán sắp xếp trộn chia mảng thành hai nửa, sắp xếp từng phần rồi trộn lại.

int temp[N];

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    int k = 0, i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (i = left, j = 0; i <= right; i++, j++) arr[i] = temp[j];
}

Tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân cho phép tìm phần tử trong mảng đã sắp xếp với độ phức tạp O(log n).

// Tìm vị trí đầu tiên thỏa mãn điều kiện
int binarySearch1(int left, int right) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

// Tìm vị trí cuối cùng thỏa mãn điều kiện
int binarySearch2(int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

Độ chính xác cao (Big Integer)

Xử lý các số nguyên lớn vượt quá giới hạn của kiểu dữ liệu cơ bản.

Phép cộng

vector<int> bigAdd(vector<int>& num1, vector<int>& num2) {
    if (num1.size() < num2.size()) return bigAdd(num2, num1);
    
    vector<int> result;
    int carry = 0;
    
    for (int i = 0; i < num1.size(); i++) {
        carry += num1[i];
        if (i < num2.size()) carry += num2[i];
        result.push_back(carry % 10);
        carry /= 10;
    }
    
    if (carry) result.push_back(carry);
    return result;
}

Phép trừ

bool compare(vector<int>& num1, vector<int>& num2) {
    if (num1.size() != num2.size()) return num1.size() > num2.size();
    for (int i = num1.size() - 1; i >= 0; i--)
        if (num1[i] != num2[i]) return num1[i] > num2[i];
    return true;
}

vector<int> bigSub(vector<int>& num1, vector<int>& num2) {
    vector<int> result;
    int borrow = 0;
    
    for (int i = 0; i < num1.size(); i++) {
        borrow = num1[i] - borrow;
        if (i < num2.size()) borrow -= num2[i];
        result.push_back((borrow + 10) % 10);
        borrow = borrow < 0 ? 1 : 0;
    }
    
    while (result.size() > 1 && result.back() == 0) result.pop_back();
    return result;
}

Phép nhân

vector<int> bigMul(vector<int>& num1, vector<int>& num2) {
    vector<int> result(num1.size() + num2.size(), 0);
    
    for (int i = 0; i < num1.size(); i++) {
        for (int j = 0; j < num2.size(); j++) {
            result[i + j] += num1[i] * num2[j];
            result[i + j + 1] += result[i + j] / 10;
            result[i + j] %= 10;
        }
    }
    
    while (result.size() > 1 && result.back() == 0) result.pop_back();
    return result;
}

Phép chia

vector<int> bigDiv(vector<int>& num1, int divisor, int& remainder) {
    vector<int> result;
    remainder = 0;
    
    for (int i = num1.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + num1[i];
        result.push_back(remainder / divisor);
        remainder %= divisor;
    }
    
    reverse(result.begin(), result.end());
    while (result.size() > 1 && result.back() == 0) result.pop_back();
    return result;
}

Phép toán trên bit

Lấy bit 1 thấp nhất của một số nguyên.

int lowBit(int x) {
    return x & -x;
}
// Ví dụ: 5 (101) & -5 (011) = 1 (001)

Tổng tiền tố (Prefix Sum)

1 chiều

const int MAXN = 100010;
int arr[MAXN], prefix[MAXN];

void buildPrefixSum(int n) {
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] + arr[i];
}

int rangeSum(int left, int right) {
    return prefix[right] - prefix[left - 1];
}

2 chiều

int matrix[MAXN][MAXN], prefix2D[MAXN][MAXN];

void build2DPrefixSum(int n, int m) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            prefix2D[i][j] = matrix[i][j] + prefix2D[i-1][j] 
                           + prefix2D[i][j-1] - prefix2D[i-1][j-1];
}

int query2D(int x1, int y1, int x2, int y2) {
    return prefix2D[x2][y2] - prefix2D[x1-1][y2] 
         - prefix2D[x2][y1-1] + prefix2D[x1-1][y1-1];
}

Mảng hiệu (Difference Array)

1 chiều

int arr[MAXN], diff[MAXN];

void buildDiffArray(int n) {
    for (int i = 1; i <= n; i++)
        diff[i] = arr[i] - arr[i - 1];
}

void rangeAdd(int left, int right, int val) {
    diff[left] += val;
    diff[right + 1] -= val;
}

void rebuildArray(int n) {
    for (int i = 1; i <= n; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }
}

2 chiều

void rangeAdd2D(int x1, int y1, int x2, int y2, int val) {
    diff[x1][y1] += val;
    diff[x2 + 1][y1] -= val;
    diff[x1][y2 + 1] -= val;
    diff[x2 + 1][y2 + 1] += val;
}

void rebuild2DArray(int n, int m) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            arr[i][j] = arr[i-1][j] + arr[i][j-1] 
                      - arr[i-1][j-1] + diff[i][j];
}

Rời rạc hóa (Discretization)

Kỹ thuật ánh xạ các giá trị lớn hoặc phân tán về chỉ số liên tiếp nhỏ hơn.

vector<int> coordinates;
vector<pair<int,int>> updates, queries;

int getCompressedIndex(int value) {
    int left = 0, right = coordinates.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (coordinates[mid] >= value) right = mid;
        else left = mid + 1;
    }
    return left + 1;
}

void discretize() {
    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());
}