Nayan PahujaToday I faced this question during the online assessment test of Innovations Trilogy in an on campus hiring.
Well then let's start DAY 64.
Question: SUBARRAYS AND OR
Given an array A of N integers and an array B of Q queries and updates. There are three type of queries which are as follows,
(i) 1 l r v Initialize every element with IN the range [l,r].
(ii) 2 l r v: Change every element x in the range [I, r] to x OR v.
(iii) 3 l r 0 : Find the sum of bitwise AND of all the subarrays in the range [l1,r1]. such that l1>=l and r1<=r.
Question Break Down and Intuition:
- Whenever we see questions like a given array and we have to apply a bunch of operations and run it through multiple queries, our mind should immediately jump to segment trees.
Question: What are segment trees? : Segment Trees
- So we have to apply a bunch of queries into some subarrays and then generate some answers on that basis cool.
- If it's of type 1 we traverse through that subsection range and update all the values to v.
- If it's of type 2 we update the values to x OR v.
- If it's of type 3 we go through every section in the range of l1 and r1 and add them all up to generate prefix sum.
Since it's easier said than done we will break the question into a few parts
Coding it out:
Building the segment tree.
- The first thing we need to do is to build a segment tree the base of all our operations.
- We need a vector named segmentTree(or Tree in code) to store the order of tree.
- We also need the original array A.
- We initialize the base case where our start == end (that is when We have reached a node where no more subsections are possible). We assign it the corresponding start value.
- else we divide it into two parts and call the function recursively.
- We get any of our tree[node] to be the bitwise operation of it's left and right subindexes.
void build_segment_tree(vector<int>& arr, vector<int>& tree, int start, int end, int node) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build_segment_tree(arr, tree, start, mid, 2 * node + 1);
build_segment_tree(arr, tree, mid + 1, end, 2 * node + 2);
tree[node] = tree[2 * node + 1] | tree[2 * node + 2];
}
}
Querying the segment tree and doing operations:
- Now on to the hard part.
- We must first identify what type of query it is, which we are getting at our queries[i][0].
- After appropriately identifying the query type we do it's operation.
- For type 1 we update the values to be val.
- For type 2 we do the bitwise OR operation.
- For type 3 we generate all it's subarrays and add their bitwise and sum.
vector<int> processQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector<int> tree(4 * n, 0); // Segment tree has 4 times size
build_segment_tree(arr, tree, 0, n - 1, 0);
vector<int> result;
for (const auto& query : queries) {
//decoding what type of query it is
int queryType = query[0];
int l = query[1];
int r = query[2];
if (queryType == 1) {
int v = query[3];
for (int i = l - 1; i < r; ++i) {
arr[i] = v;
}
build_segment_tree(arr, tree, 0, n - 1, 0);
} else if (queryType == 2) {
int v = query[3];
for (int i = l - 1; i < r; ++i) {
arr[i] |= v;
}
build_segment_tree(arr, tree, 0, n - 1, 0);
} else if (queryType == 3) {
int sum_of_and = 0;
for (int i = l - 1; i < r; ++i) {
for (int j = i; j < r; ++j) {
int subarray_and = arr[i];
for (int k = i + 1; k <= j; ++k) {
subarray_and &= arr[k];
}
sum_of_and += subarray_and;
}
}
result.push_back(sum_of_and);
}
}
return result;
}
Full Code with example:
#include <iostream>
#include <vector>
using namespace std;
void build_segment_tree(vector<int>& arr, vector<int>& tree, int start, int end, int ind) {
if (start == end) {
tree[ind] = arr[start];
} else {
int mid = (start + end) / 2;
build_segment_tree(arr, tree, start, mid, 2 * ind + 1);
build_segment_tree(arr, tree, mid + 1, end, 2 * ind + 2);
tree[ind] = tree[2 * ind + 1] | tree[2 * ind + 2];
}
}
vector<int> processQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector<int> tree(4 * n, 0); // Segment tree has 4 times size
build_segment_tree(arr, tree, 0, n - 1, 0);
vector<int> result;
for (const auto& query : queries) {
//decoding what type of query it is
int queryType = query[0];
int l = query[1];
int r = query[2];
if (queryType == 1) {
int v = query[3];
for (int i = l - 1; i < r; ++i) {
arr[i] = v;
}
build_segment_tree(arr, tree, 0, n - 1, 0);
} else if (queryType == 2) {
int v = query[3];
for (int i = l - 1; i < r; ++i) {
arr[i] |= v;
}
build_segment_tree(arr, tree, 0, n - 1, 0);
} else if (queryType == 3) {
int sum_of_and = 0;
for (int i = l - 1; i < r; ++i) {
for (int j = i; j < r; ++j) {
int subarray_and = arr[i];
for (int k = i + 1; k <= j; ++k) {
subarray_and &= arr[k];
}
sum_of_and += subarray_and;
}
}
result.push_back(sum_of_and);
}
}
return result;
}
int main() {
vector<int> A = {1, 0, 2, 5};
vector<vector<int>> queries = {{3, 1, 3, 0}, {1, 1, 2, 4}, {2, 2, 4, 5}, {3, 1, 4, 0}};
vector<int> result = processQueries(A, queries);
for (int ans : result) {
cout << ans << " ";
}
cout << endl;
return 0;
}
Complexity Analysis:
Time: O(Q*N^3) We can optimize it but I am only looking to provide a basic outlook as I am still testing out my solution.
Space: O(4*N)
I was unable to solve it and I must say it's a difficult question and lot of code to write in an assessment but nevertheless.
This is the code that I have come to. Please feel free to correct me if I am wrong at any place.
Thanks for reading. Peace out.
