# **Prefix OR ?**
Người ra đề: Nguyễn Quang Huy
Người làm solution: Hoàng Tấn Phúc
Ta có bảng giá trị chân lý của phép toán OR như sau:
**A B    A OR B**
0 0        0
0 1        1
1 0        1
1 1        1
Dựa vào bảng trên, dễ dàng thấy được bit thu được từ phép toán A OR B bằng 1 khi và chỉ khi có ít nhất 1 bit có giá trị 1. Vì vậy, khi ta thực hiện phép toán OR trên một dãy bit, chỉ cần xuất hiện 1 bit có giá trị bằng 1 thì kết quả sẽ bằng 1. Còn nếu không xuất hiện bit có trị 1 nào, thì kết quả sẽ là 0. Ta sẽ kiểm tra sự có mặt của bit 1 đơn giản bằng việc tính tổng dãy số.
Để trả lời nhanh tổng của một dãy bit trên đoạn [l, r], ta sử dụng tổng tiền tố (prefix sum).
Dữ liệu đề bài đảm bảo giới hạn số nguyên không vượt quá 2^{30}, nghĩa là ta có thể biểu diễn các số nguyên đó bằng 30 bit nhị phân. Vì vậy ta có thể tạo 30 mảng tổng tiền tố để thực hiện truy vấn cho mỗi bit.