Tìm số mảng con có bitwise OR lớn hơn hoặc bằng K bằng C++

Trong bài viết này, chúng ta sẽ giải thích cách tìm số lượng mảng con có phép OR bitwise lớn hơn hoặc bằng K bằng C++. Cho mảng arr[] và số nguyên K, yêu cầu đếm các mảng con mà kết quả OR của các phần tử trong mảng con ≥ K. Ví dụ:

Input: arr[] = {1, 2, 3} K = 3 Output: 4
Bitwise OR của các mảng con:
{1} = 1, {1, 2} = 3, {1, 2, 3} = 3
{2} = 2, {2, 3} = 3, {3} = 3
4 mảng con có bitwise OR ≥ 3

Input: arr[] = {3, 4, 5} K = 6 Output: 2

Các phương pháp giải quyết

1. Phương pháp Brute Force

Duyệt qua tất cả mảng con, tính OR bitwise và so sánh với K. Nếu ≥ K thì tăng biến đếm.

Ví dụ mã nguồn

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

int main() {
    int arr[] = {1, 2, 3};
    int k = 3;
    int size = sizeof(arr) / sizeof(int);
    int answer = 0;

    for (int i = 0; i < size; i++) {
        int bitwise = 0;
        for (int j = i; j < size; j++) {
            bitwise = bitwise | arr[j];
            if (bitwise >= k)
                answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

Kết quả

4

Phương pháp này đơn giản nhưng độ phức tạp O(N²), không phù hợp với ràng buộc lớn.

2. Phương pháp hiệu quả (Binary Search + Segment Tree)

Tận dụng tính chất của phép OR: kết quả OR không bao giờ giảm khi thêm phần tử mới. Nếu mảng con từ i đến j có OR ≥ K, thì mọi mảng con bao gồm đoạn [i, j] cũng sẽ có OR ≥ K. Ta dùng Segment Tree để truy vấn OR trên đoạn trong O(log N), kết hợp Binary Search để tìm vị trí j nhỏ nhất sao cho OR[i..j] ≥ K. Số mảng con bắt đầu tại i thỏa mãn là N - j.

Ví dụ mã nguồn

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

int t[4 * N];

void build(int *a, int v, int start, int end) {
    if (start == end) {
        t[v] = a[start];
        return;
    }
    int mid = (start + end) / 2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) return t[v];
    int tm = (tl + tr) / 2;
    int q1 = query(2 * v, tl, tm, l, min(tm, r));
    int q2 = query(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
    return q1 | q2;
}

int main() {
    int arr[] = {1, 2, 3};
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]);
    int answer = 0;
    build(arr, 1, 0, size - 1);

    for (int i = 0; i < size; i++) {
        int start = i, end = size - 1;
        int ind = INT_MAX;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (query(1, 0, size - 1, i, mid) >= k) {
                ind = min(mid, ind);
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (ind != INT_MAX)
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}

Kết quả

4

Độ phức tạp thời gian giảm từ O(N²) xuống O(N log N), phù hợp cho dữ liệu lớn.

Kết luận

Bài viết đã giải quyết bài toán đếm mảng con có bitwise OR ≥ K trong O(N log N) bằng Binary Search và Segment Tree. Mã nguồn C++ và giải thuật chi tiết đã được trình bày. Có thể triển khai tương tự bằng C, Java, Python và các ngôn ngữ khác.