คิวรีสำหรับจำนวนองค์ประกอบในช่วงที่มี Kth Bit Set ใช้ C++

ในบทความนี้ เราจะอภิปรายปัญหาการหาจำนวนองค์ประกอบที่อยู่ในช่วงที่กำหนดซึ่งมี kth bit ตั้งค่าไว้ ตัวอย่างเช่น:

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

เราจะแก้ปัญหานี้ด้วยวิธี Brute Force และดูว่าวิธีนี้สามารถทำงานกับข้อจำกัดที่สูงกว่าได้หรือไม่ ถ้าไม่ได้ เราจะพยายามคิดวิธีที่มีประสิทธิภาพใหม่

วิธี Brute Force

ในวิธีนี้ เราจะเพียงแค่เดินทางผ่านช่วงและตรวจสอบแต่ละองค์ประกอบว่ามี kth bit ตั้งค่าไว้หรือไม่ ถ้ามี เราเพิ่มตัวนับ

ตัวอย่าง

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

#define MAX_BITS 32

bool Kset(int n, int k) { // ตรวจสอบว่า kth bit ตั้งค่าไว้หรือไม่
    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] = { // L, R และ k ที่กำหนด
        { 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;
}

ผลลัพธ์

0 1

วิธีข้างต้นมีความซับซ้อนด้านเวลา O(N×Q) โดยที่ N คือขนาดของอาร์เรย์ และ Q คือจำนวนคิวรี ตอนนี้คุณเห็นได้ว่าวิธีนี้ไม่เหมาะสำหรับข้อจำกัดที่สูงกว่า เพราะจะใช้เวลามากเกินไป ดังนั้นตอนนี้เราจะพยายามทำโปรแกรมวิธีที่มีประสิทธิภาพ

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะสร้างอาร์เรย์ prefix sum 2 มิติ ที่จะเก็บจำนวนของแต่ละ bit ที่ใช้จนถึงแต่ละดัชนี และจากนั้นเราสามารถคำนวณคำตอบได้ในความซับซ้อน O(1)

ตัวอย่าง

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

#define bits 32 // จำนวน bit
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[]) { // สร้าง prefix array
    for (int i = 0; i <= bits; i++) {
        P[0][i] = 0; // ตั้งค่าจำนวนเริ่มต้นของทุก bit = 0
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= bits; j++) {
            bool flag = Kset(arr[i], j);
            if (i) // เราเพิ่มจำนวนก่อนหน้าเข้ากับจำนวนล่าสุด(0)
                P[i][j] = P[i - 1][j];
            if (flag) { // ถ้า jth bit ตั้งค่าไว้ เราเพิ่มจำนวน
                P[i][j]++;
            }
        }
    }
}

int query(int L, int R, int K) {
    if (L) // ถ้า L ไม่เท่ากับ 0 คืนค่า prefix ที่ R ลบด้วย prefix ที่ L-1
        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); // เรียกฟังก์ชันเพื่อสร้าง prefix array
    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;
}

ผลลัพธ์

2 3

เนื่องจากเราสร้าง prefix array ที่ช่วยให้เราหาคำตอบได้ใน O(1) ดังนั้นความซับซ้อนด้านเวลาของเราลดลงอย่างมากเหลือ O(N) โดยที่ N คือขนาดของอาร์เรย์ที่กำหนด

คำอธิบายโค้ด

ในโปรแกรมนี้ เราสร้าง prefix counter สำหรับทุกดัชนีของอาร์เรย์ ที่นับทุก bit ที่ใช้จนถึงดัชนีนั้น เราสร้างจำนวนนี้สำหรับอาร์เรย์ของเรา ตอนนี้เรามี prefix count ของทุก bit เก็บไว้แล้ว สำหรับ kth bit count เราต้องลบ prefix count ของ kth bit จนถึงดัชนี R ด้วย prefix count ของ kth bit จนถึงดัชนี L-1 และนั่นคือคำตอบของเรา

สรุป

ในบทความนี้ เราแก้ปัญหา Queries สำหรับจำนวนองค์ประกอบในอาร์เรย์ในช่วงที่มี Kth Bit Set เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์