Truy vấn số phần tử có bit thứ K = 1 trong khoảng [L, R] bằng C++

Cho mảng, cần trả lời truy vấn: đếm số phần tử trong đoạn [L, R] có bit thứ K (từ 1) bằng 1. Ví dụ:

Input : arr[] = { 4, 5, 7, 2 } Query 1: L = 2, R = 4, K = 4 Query 2: L = 3, R = 5, K = 1 Output : 0  1

Cách vét cạn (Brute Force)

Duyệt từng phần tử trong [L, R], kiểm tra bit K bằng (n & (1 << (k-1))). Độ phức tạp O(N×Q).

Ví dụ

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

bool Kset(int n, int k) {
    if (n & (1 << (k - 1))) return true;
    return false;
}

int query(int L, int R, int K, int arr[]) {
    int count = 0;
    for (int i = L; i <= R; i++)
        if (Kset(arr[i], K)) count++;
    return count;
}

int main() {
    int arr[] = { 4, 5, 7, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int queries[][3] = { { 2, 4, 4 }, { 3, 5, 1 } };
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; i++) {
        int L = queries[i][0] - 1;
        int R = queries[i][1] - 1;
        int K = queries[i][2];
        cout << query(L, R, K, arr) << "\n";
    }
    return 0;
}

Kết quả

0 1

Cách hiệu quả: Mảng tiền tố 2D (Prefix Bit Count)

Xây dựng P[i][b] = số phần tử từ đầu đến chỉ số i có bit b = 1. Truy vấn [L, R] bit K: P[R][K] - P[L-1][K] (O(1)).

Ví dụ

#include<bits/stdc++.h>
using namespace std;
#define bits 32
int P[100000][bits+1];

bool Kset(int n, int k) {
    if (n & (1 << (k - 1))) return true;
    return false;
}

void prefixArray(int n, int arr[]) {
    for (int i = 0; i <= bits; i++) P[0][i] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= bits; j++) {
            bool flag = Kset(arr[i], j);
            if (i) P[i][j] = P[i-1][j];
            if (flag) P[i][j]++;
        }
    }
}

int query(int L, int R, int K) {
    if (L) return P[R][K] - P[L-1][K];
    else return P[R][K];
}

int main() {
    int arr[] = { 8, 9, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int queries[][3] = { { 1, 3, 4 }, { 2, 4, 1 } };
    prefixArray(n, arr);
    int q = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < q; i++) {
        int L = queries[i][0] - 1;
        int R = queries[i][1] - 1;
        int K = queries[i][2];
        cout << query(L, R, K) << "\n";
    }
    return 0;
}

Kết quả

2 3

Giải thích

Mảng P lưu số lần từng bit xuất hiện đến chỉ số i. Trừ hai tiền tố cho kết quả O(1). Tổng độ phức tạp O(N×32 + Q) ≈ O(N+Q).

Kết luận

Giải quyết truy vấn đếm bit K trong khoảng bằng Prefix Bit Count 2D. Cách vét cạn O(NQ) và cách tối ưu O(N+Q) kèm code C++.