คิวรีสำหรับ Bitwise AND ในช่วงดัชนี [L, R] ของอาร์เรย์ที่กำหนด ใช้ C++

ในบทความนี้ เราได้รับปัญหาที่เราได้รับอาร์เรย์ของจำนวนเต็ม และเราถูกมอบหมายให้หา bitwise AND ของช่วงที่กำหนด ตัวอย่างเช่น:

Input: arr[] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[] = {{0, 1}, {3, 5}}
Output: 1 0
0 1 AND 31 = 1
23 AND 34 AND 4 = 00

Input: arr[] = {1, 2, 3, 4, 510, 10, 12, 16, 8}, q[] = {{0, 42}, {1, 33, 4}}
Output: 0 8 0

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

วิธี Brute Force

ในวิธีที่กำหนด เราจะเดินทางผ่านช่วงที่กำหนดและหาคำตอบของเราและพิมพ์มัน

ตัวอย่าง

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

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int); // ขนาดของอาร์เรย์
    int queries[][2] = { {0, 2}, {3, 4} }; // คิวรีที่กำหนด
    int q = sizeof(queries) / sizeof(queries[0]); // จำนวนคิวรี
    
    for(int i = 0; i < q; i++) { // เดินทางผ่านคิวรีทั้งหมด
        long ans = 1LL << 32;
        ans -= 1; // ทำให้ทุก bit ของ ans เป็น 1
        for(int j = queries[i][0]; j <= queries[i][1]; j++) // เดินทางผ่านช่วง
            ans &= ARR[j]; // คำนวณคำตอบ
        cout << ans << "\n";
    }
    return 0;
}

ผลลัพธ์

8 0

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

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

ในปัญหานี้ เราคำนวณ prefix bit count ของอาร์เรย์ล่วงหน้า เพื่อคำนวณ bitwise AND ของช่วงที่กำหนดโดยตรวจสอบส่วนร่วมของ set bits ในช่วงที่กำหนด

ตัวอย่าง

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

#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];

void bitcount(int *ARR, int n) { // สร้าง prefix counts
    for (int j = 31; j >= 0; j--) {
        prefixbits[j][0] = ((ARR[0] >> j) & 1);
        for (int i = 1; i < n; i++) {
            prefixbits[j][i] = ARR[i] & (1LL << j);
            prefixbits[j][i] += prefixbits[j][i - 1];
        }
    }
    return;
}

int check(int l, int r) { // คำนวณคำตอบ
    long ans = 0; // เพื่อหลีกเลี่ยง overflow เราใช้ long
    for (int i = 0; i < 32; i++){
        int x;
        if (l == 0)
            x = prefixbits[i][r];
        else
            x = prefixbits[i][r] - prefixbits[i][l - 1];
        if (x == r - l + 1)
            ans = ans | 1LL << i;
    }
    return ans;
}

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int); // ขนาดของอาร์เรย์
    memset(prefixbits, 0, sizeof(prefixbits)); // เริ่มต้นทุกองค์ประกอบด้วย 0
    bitcount(ARR, n);
    int queries[][2] = {{0, 2}, {3, 4}}; // คิวรีที่กำหนด
    int q = sizeof(queries) / sizeof(queries[0]); // จำนวนคิวรี
    
    for (int i = 0; i < q; i++) {
        cout << check(queries[i][0], queries[i][1]) << "\n";
    }
    return 0;
}

ผลลัพธ์

2 0

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

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

ในวิธีนี้ เราคำนวณ prefix bits count ทั้งหมดและเก็บไว้ในดัชนี ตอนนี้เมื่อเราคำนวณคิวรี เราเพียงแค่ต้องตรวจสอบว่า bit ไหนมีจำนวนเท่ากับจำนวนองค์ประกอบที่อยู่ในช่วงหรือไม่ ถ้าใช่ เราตั้งค่า bit นี้เป็น 1 ใน x ของเรา และถ้าไม่ เราเว้น bit นั้นไว้ เพราะถ้าตัวเลขใดตัวเลขหนึ่งในช่วงที่กำหนดมี bit นั้นเป็น 0 bitwise AND ทั้งหมดของ bit นั้นจะเป็นศูนย์ และนั่นคือวิธีที่เราคำนวณ bitwise AND

สรุป

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