Queries for Sum of Bitwise AND of all Subarrays in a Range

Given an array arr[] of size N, the task is to answer a set of Q queries, each in the format of queries[i][0] and queries[i][1]. For each queries[i], find the sum of Bitwise AND of all subarrays whose elements lie in the range [queries[i][0], queries[i][1]].

Examples:

Input: N = 3, arr[] = {1, 0, 2}, Q = 2, queries[][] = {{1, 2}, {2, 3}}
Output: 1 2
Explanation:

• For the first query AND[1] + AND[0] + AND[1, 0] = 1.
• For the second query AND[0] + AND[2] + AND[0, 2] = 2.

Input: N = 4, arr[] = {4, 3, 2, 1}, Q = 3, queries[][] = {{1, 3}, {2, 4}, {1, 4}}
Output: 11 8 12
Explanation:

• For the first query AND[4] + AND[3] + AND[2] + AND[4, 3] + AND[4, 3, 2] + AND[3, 2] = 11.
• For the second query AND[3] + AND[2] + AND[1] + AND[3, 2] + AND[3, 2, 1] + AND[2, 1] = 8.
• For the third query AND[4] + AND[3] + AND[2] + AND[1] + AND[4, 3] + AND[4, 3, 2] + AND[4, 3, 2, 1] + AND[3, 2] + AND[3, 2, 1] + AND[2, 1] = 12.

Approach: This can be solved with the following idea:

The main idea is to use precomputation to optimize the Bitwise AND calculation for subarrays. This is achieved by maintaining arrays that store the count and cumulative sum of consecutive set bits in the binary representation of the array elements. The final result is computed by considering the contributions of each bit position separately.

Step-by-step algorithm:

• Create two 2D arrays, pref[20][N] and next[20][N] where N is the length of array arr[].
• pref[j][i] will store the count and cumulative sum of set bits in the binary representation of arr[i] at bit position j.
• next[j][i] will store the next index with a set bit to the right of index i.
• Iterate Through Bits and Array Elements, for each bit position j from 0 to 19:
  • Calculate the count of set bits at bit position j in arr[i].
  • Update pref[j][i] with the count and cumulative sum of set bits.
  • Update next[j][i] with the next index having a set bit to the right of index i.
• Iterate through each bit position j (from 0 to 19) and calculate the values for pref[][] and next[][] based on the binary representation of array elements.
• Initialize an empty vector ans to store the results.
• For each query [u, v], iterate through each bit position j and compute the contribution of the set bits at position j within the subarray [u, v]. Update the result by adding the contribution multiplied by 2^j.
• Append the final result to the ans vector.
• Return the ans vector containing the results for all queries.

Below is the implementation of the algorithm:

#include <bits/stdc++.h> using namespace std; // Function to find sum of AND vector<long long> summationOfAnd(int N, vector<int>& arr, int Q, vector<vector<int> >& queries) { // Declare a 2D vector vector<vector<pair<int, int> > > pref( 20, vector<pair<int, int> >(N)); vector<vector<int> > next(20, vector<int>(N, 0)); // Start Iterating for (int j = 0; j < 20; j++) { int curr = 0, sum = 0; // Iterate in array for (int i = 0; i < N; i++) { // Get the AND value if ((arr[i] & (1 << j)) > 0) { curr++; sum += curr; pref[j][i] = { curr, sum }; } else { // If curr value is greater than 0 if (curr > 0) { next[j][i - 1] = i - 1; } // Set the value to 0 // for next iteration curr = 0; pref[j][i] = { curr, sum }; } } // Update the value in next vector next[j][N - 1] = N - 1; // Start Iterating from n -2 for (int i = N - 2; i >= 0; i--) { if (next[j][i] == 0) { next[j][i] = next[j][i + 1]; } } } vector<long long> ans; // Iterate in B for (int i = 0; i < Q; i++) { int u = queries[i][0] - 1; int v = queries[i][1] - 1; long long res = 0; // Iterate again for 20 times for (int j = 0; j < 20; j++) { long long temp; // Get the temp value if (u == 0) { temp = pref[j][v].second; } else if (pref[j][u].first == 0) { temp = pref[j][v].second - pref[j][u].second; } else { // Minumum value for right int right = min(v, next[j][u]); temp = pref[j][v].second - pref[j][right].second; if (pref[j][right].first > 0) { temp += (right - u + 1) * (right - u + 2) / 2; } } // Add the value to res res += (temp * (1 << j)); } // Store it in ans ans.push_back(res); } // Return vector ans return ans; } // Driver code int main() { int N = 4; vector<int> arr = { 4, 3, 2, 1 }; int Q = 3; vector<vector<int> > queries = { { 1, 3 }, { 2, 4 }, { 1, 4 } }; // Function call vector<long long> ans = summationOfAnd(N, arr, Q, queries); for (auto a : ans) { cout << a << " "; } return 0; } 

import java.util.*; public class Main { // Function to find sum of AND static List<Long> summationOfAnd(int N, List<Integer> arr, int Q, List<List<Integer>> queries) { // Declare a 2D vector List<List<Pair>> pref = new ArrayList<>(20); List<List<Integer>> next = new ArrayList<>(20); for (int i = 0; i < 20; i++) { pref.add(new ArrayList<>(Collections.nCopies(N, new Pair(0, 0)))); next.add(new ArrayList<>(Collections.nCopies(N, 0))); } // Start iterating for (int j = 0; j < 20; j++) { int curr = 0, sum = 0; // Iterate in array for (int i = 0; i < N; i++) { // Get the AND value if ((arr.get(i) & (1 << j)) > 0) { curr++; sum += curr; pref.get(j).set(i, new Pair(curr, sum)); } else { // If curr value is greater than 0 if (curr > 0) { next.get(j).set(i - 1, i - 1); } // Set the value to 0 for next iteration curr = 0; pref.get(j).set(i, new Pair(curr, sum)); } } // Update the value in next list next.get(j).set(N - 1, N - 1); // Start Iterating from n -2 for (int i = N - 2; i >= 0; i--) { if (next.get(j).get(i) == 0) { next.get(j).set(i, next.get(j).get(i + 1)); } } } List<Long> ans = new ArrayList<>(); // Iterate in B for (List<Integer> query : queries) { int u = query.get(0) - 1; int v = query.get(1) - 1; long res = 0; // Iterate again for 20 times for (int j = 0; j < 20; j++) { long temp; // Get the temp value if (u == 0) { temp = pref.get(j).get(v).second; } else if (pref.get(j).get(u).first == 0) { temp = pref.get(j).get(v).second - pref.get(j).get(u).second; } else { // Minimum value for right int right = Math.min(v, next.get(j).get(u)); temp = pref.get(j).get(v).second - pref.get(j).get(right).second; if (pref.get(j).get(right).first > 0) { temp += (right - u + 1) * (right - u + 2) / 2; } } // Add the value to res res += (temp * (1L << j)); } // Store it in ans ans.add(res); } // Return list ans return ans; } // Pair class to store pair values static class Pair { int first; int second; Pair(int first, int second) { this.first = first; this.second = second; } } // Driver code public static void main(String[] args) { int N = 4; List<Integer> arr = Arrays.asList(4, 3, 2, 1); int Q = 3; List<List<Integer>> queries = Arrays.asList(Arrays.asList(1, 3), Arrays.asList(2, 4), Arrays.asList(1, 4)); // Function call List<Long> ans = summationOfAnd(N, arr, Q, queries); // Print the result for (long a : ans) { System.out.print(a + " "); } } } 

using System; using System.Collections.Generic; class Solution { // Function to find sum of AND static List<long> SummationOfAnd(int N, List<int> arr, int Q, List<List<int>> queries) { // Declare a 2D list List<List<Tuple<int, int>>> pref = new List<List<Tuple<int, int>>>(); List<List<int>> next = new List<List<int>>(); // Initialize pref and next lists for (int i = 0; i < 20; i++) { pref.Add(new List<Tuple<int, int>>()); next.Add(new List<int>()); for (int j = 0; j < N; j++) { pref[i].Add(new Tuple<int, int>(0, 0)); next[i].Add(0); } } // Start Iterating for (int j = 0; j < 20; j++) { int curr = 0, sum = 0; // Iterate in array for (int i = 0; i < N; i++) { // Get the AND value if ((arr[i] & (1 << j)) > 0) { curr++; sum += curr; pref[j][i] = new Tuple<int, int>(curr, sum); } else { // If curr value is greater than 0 if (curr > 0) { next[j][i - 1] = i - 1; } // Set the value to 0 for next iteration curr = 0; pref[j][i] = new Tuple<int, int>(curr, sum); } } // Update the value in next vector next[j][N - 1] = N - 1; // Start Iterating from n -2 for (int i = N - 2; i >= 0; i--) { if (next[j][i] == 0) { next[j][i] = next[j][i + 1]; } } } List<long> ans = new List<long>(); // Iterate in B for (int i = 0; i < Q; i++) { int u = queries[i][0] - 1; int v = queries[i][1] - 1; long res = 0; // Iterate again for 20 times for (int j = 0; j < 20; j++) { long temp; // Get the temp value if (u == 0) { temp = pref[j][v].Item2; } else if (pref[j][u].Item1 == 0) { temp = pref[j][v].Item2 - pref[j][u].Item2; } else { // Minimum value for right int right = Math.Min(v, next[j][u]); temp = pref[j][v].Item2 - pref[j][right].Item2; if (pref[j][right].Item1 > 0) { temp += (right - u + 1) * (right - u + 2) / 2; } } // Add the value to res res += (temp * (1 << j)); } // Store it in ans ans.Add(res); } // Return vector ans return ans; } // Driver code static void Main(string[] args) { int N = 4; List<int> arr = new List<int> { 4, 3, 2, 1 }; int Q = 3; List<List<int>> queries = new List<List<int>> { new List<int> { 1, 3 }, new List<int> { 2, 4 }, new List<int> { 1, 4 } }; // Function call List<long> ans = SummationOfAnd(N, arr, Q, queries); foreach (long a in ans) { Console.Write(a + " "); } } } 

function GFG(N, arr, Q, queries) { // Declare variables let pref = new Array(20).fill(null).map(() => new Array(N).fill(null)); let next = new Array(20).fill(null).map(() => new Array(N).fill(0)); // Start Iterating for (let j = 0; j < 20; j++) { let curr = 0, sum = 0; // Iterate over array for (let i = 0; i < N; i++) { // Get the AND value if ((arr[i] & (1 << j)) > 0) { curr++; sum += curr; pref[j][i] = [curr, sum]; } else { // If curr value is greater than 0 if (curr > 0) { next[j][i - 1] = i - 1; } curr = 0; pref[j][i] = [curr, sum]; } } // Update the value in next vector next[j][N - 1] = N - 1; // Start Iterating from n -2 for (let i = N - 2; i >= 0; i--) { if (next[j][i] == 0) { next[j][i] = next[j][i + 1]; } } } let ans = []; // Iterate over queries for (let i = 0; i < Q; i++) { let u = queries[i][0] - 1; let v = queries[i][1] - 1; let res = 0; // Iterate again for 20 times for (let j = 0; j < 20; j++) { let temp; // Get the temp value if (u === 0) { temp = pref[j][v][1]; } else if (pref[j][u][0] === 0) { temp = pref[j][v][1] - pref[j][u][1]; } else { // Minumum value for right let right = Math.min(v, next[j][u]); temp = pref[j][v][1] - pref[j][right][1]; if (pref[j][right][0] > 0) { temp += (right - u + 1) * (right - u + 2) / 2; } } // Add the value to res res += (temp * (1 << j)); } // Store it in ans ans.push(res); } // Return vector ans return ans; } // Driver code function main() { let N = 4; let arr = [4, 3, 2, 1]; let Q = 3; let queries = [[1, 3], [2, 4], [1, 4]]; // Function call let ans = GFG(N, arr, Q, queries); // Print the result let output = ""; for (let a of ans) { output += a + " "; } console.log(output.trim()); // Trim to remove trailing space } // Invoke main function main(); 

def solve(N, arr, Q, queries): pref = [[[0, 0] for _ in range(N)] for _ in range(20)] next = [[0 for _ in range(N)] for _ in range(20)] for j in range(20): curr, sum = 0, 0 for i in range(N): if arr[i] & (1 << j): curr += 1 sum += curr pref[j][i] = [curr, sum] else: if curr > 0: next[j][i - 1] = i - 1 curr = 0 pref[j][i] = [curr, sum] next[j][N - 1] = N - 1 for i in range(N - 2, -1, -1): if next[j][i] == 0: next[j][i] = next[j][i + 1] ans = [] for u, v in queries: u -= 1 v -= 1 res = 0 for j in range(20): if u == 0: temp = pref[j][v][1] elif pref[j][u - 1][0] == 0: temp = pref[j][v][1] - pref[j][u - 1][1] else: right = min(v, next[j][u - 1]) temp = pref[j][v][1] - pref[j][right][1] if pref[j][right][0] > 0: temp += (right - u + 1) * (right - u + 2) // 2 res += temp * (1 << j) ans.append(res) return ans # Driver code if __name__ == "__main__": N = 4 arr = [4, 3, 2, 1] Q = 3 queries = [(1, 3), (2, 4), (1, 4)] ans = solve(N, arr, Q, queries) for a in ans: print(a, end=" ") 

11 8 12 

Time Complexity: O(N + Q), where N is the size of input array arr[] and Q is the number of queries.
Auxiliary Space: O(N)