DAY 64 - SUBARRAYS AND OR PROBLEM
Tags: interview, coding, datastructures, algorithms
Published: 2023-08-06 19:35:39

Today 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](https://www.geeksforgeeks.org/segment-tree-data-structure/)

- 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.