Find Array after Q queries where in each query change a[i] to a[i] | x

Namachila October 13, 2025

0 0 8 minutes read

Given an array of N elements, initially all a[i] = 0. Q queries need to be performed. Each query contains three integers l, r, and x and you need to change all a[i] to (a[i] | x) for all l ≤ i ≤ r and return the array after executing Q queries.

Examples:

Input: N = 3, Q = 2, U = {{1, 3, 1}, {1, 3, 2}}
Output: a[] = {3, 3, 3}
Explanation: Initially, all elements of the array are 0. After execution of the first query, all elements become 1 and after execution of the second query all elements become 3.

Input: N = 3, Q = 2, U = {{1, 2, 1}, {3, 3, 2}}
Output: a[] = {1, 1, 2}
Explanation: {0, 0, 0] => {1, 1, 0} => {1, 1, 2}

Naive Approach:

Initialize the array a of the size N with all elements set to 0.
For each query in U:
– Iterate over the range from the l to r (inclusive).
– For each index i, perform the bitwise OR operation between the current value at a[i] and x, and update a[i] with the result.
Return the final array a after executing all queries.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to perform operations on an array based on given
// queries
vector<int> GFG(int N, int Q, vector<vector<int> >& U)
{
    vector<int> a(N, 0);
 
    // Process each query in U
    for (const auto& query : U) {
        // Start index of range
        int l = query[0];
 
        // End index of range
        int r = query[1];
 
        // Value to be ORed
        int x = query[2];
 
        // Perform OR operation on elements within the range
        // [l, r]
        for (int i = l - 1; i < r; ++i) {
            a[i] |= x;
        }
    }
 
    return a;
}
 
int main()
{
    // Number of elements in the array
    int N = 3;
 
    // Number of queries
    int Q = 2;
    vector<vector<int> > U
        = { { 1, 2, 1 },
            { 3, 3, 2 } }; // Queries: [l, r, x]
 
    // Call the function to perform operations on the array
    vector<int> result = GFG(N, Q, U);
 
    // Print the resulting array
    for (const auto& num : result) {
        cout << num << " ";
    }
    cout << endl;
 
    return 0;
}

Java

// Java code for the above approach:
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    // Function to perform operations on an array based on given 
    // queries
    public static List<Integer> GFG(int N, int Q, List<List<Integer>> U) {
        List<Integer> a = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            a.add(0);
        }
 
        // Process each query in U
        for (List<Integer> query : U) {
            // Start index of range
            int l = query.get(0);
 
            // End index of range
            int r = query.get(1);
 
            // Value to be ORed
            int x = query.get(2);
 
            // Perform OR operation on elements within the range 
            // [l, r]
            for (int i = l - 1; i < r; i++) {
                a.set(i, a.get(i) | x);
            }
        }
 
        return a;
    }
 
    public static void main(String[] args) {
        // Number of elements in the array
        int N = 3;
 
        // Number of queries
        int Q = 2;
        List<List<Integer>> U = new ArrayList<>();
        U.add(List.of(1, 2, 1));
        U.add(List.of(3, 3, 2)); // Queries: [l, r, x]
 
        // Call the function to perform operations on the array
        List<Integer> result = GFG(N, Q, U);
 
        // Print the resulting array
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
 
 
// This code is contributed by Utkarsh Kumar

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Function to perform operations on an 
    // array based on given queries
    static List<int> Geek(int N, int Q, List<List<int>> U)
    {
        List<int> a = new List<int>(new int[N]);
        // Process each query in U
        foreach (var query in U)
        {
            // Start index of range
            int l = query[0];
            // End index of range
            int r = query[1];
            // Value to be ORed
            int x = query[2];
            // Perform OR operation on elements within 
            // the range [l, r]
            for (int i = l - 1; i < r; ++i)
            {
                a[i] |= x;
            }
        }
        return a;
    }
    static void Main(string[] args)
    {
        // Number of elements in the array
        int N = 3;
        // Number of queries
        int Q = 2;
        List<List<int>> U = new List<List<int>>
        {
            new List<int> { 1, 2, 1 },
            new List<int> { 3, 3, 2 },
        }; // Queries: [l, r, x]
        List<int> result = Geek(N, Q, U);
        // Print the resulting array
        foreach (var num in result)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

Output

1 1 2

Time complexity: O(N * Q), where N is the number of elements in the array and Q is the number of queries.
Auxiliary space: O(N) because it uses an additional vector a to store the resulting array of size N.

Efficient Approach:

To solve this problem efficiently, we have to use the concept of difference arrays for each bit.

Below are the steps for the above approach:

Create a 2D difference array say, dp[][] of size N*20. For every index, keep an array of size 20 to store the bits and initialize every index as 0.
For each query of l, r, and x, increment those indices of the dp[l] array where the bit position of x is set and decrement those indexes of the dp[r+1] array where the bit position of x is set.
For each bit, we will run a loop from i=1 to N. And add the value of the previous index to the value of the current index, dp[i][j] += dp[i-1][j].
Declare an array, say a[] which will be the answer array.
Every inner array of dp[][] array represents a number. That means every index of the inner array represents the bit of a number. So put the numbers in their appropriate positions and return them.

Below is the implementation of the above approach:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
vector<int> updateQuery(int N, int Q,
                        vector<vector<int> >& U)
{
 
    // Code here
    vector<int> a(N);
    fill(a.begin(), a.end(), 0);
    int dp[N][20];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 20; j++)
            dp[i][j] = 0;
    }
    for (int j = 0; j < U.size(); j++) {
        for (int i = 0; i < 20; i++) {
            if (U[j][2] & (1 << i)) {
                dp[U[j][0] - 1][i]++;
                if (U[j][1] < N)
                    dp[U[j][1]][i]--;
            }
        }
    }
    for (int j = 0; j < 20; j++) {
        for (int i = 1; i < N; i++) {
            dp[i][j] += dp[i - 1][j];
        }
    }
    for (int i = 0; i < N; i++) {
        int ans = 0;
        for (int j = 0; j < 20; j++) {
            if (dp[i][j])
                ans += (1 << j);
        }
        a[i] = ans;
    }
    return a;
}
 
// Drivers code
int main()
{
 
    int N = 3, Q = 2;
    vector<vector<int> > u = { { 1, 2, 1 }, { 3, 3, 2 } };
 
    // Function Call
    vector<int> ans = updateQuery(N, Q, u);
    for (auto it : ans)
        cout << it << " ";
    return 0;
}

Java

// Java code for the above approach:
 
import java.util.*;
 
class GFG {
    public static void main(String[] args) {
        int N = 3, Q = 2;
        List<List<Integer>> U = new ArrayList<>();
        U.add(Arrays.asList(1, 2, 1));
        U.add(Arrays.asList(3, 3, 2));
 
        List<Integer> ans = updateQuery(N, Q, U);
        for (int it : ans)
            System.out.print(it + " ");
    }
 
    static List<Integer> updateQuery(int N, int Q, List<List<Integer>> U) {
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < N; i++)
            a.add(0);
 
        int[][] dp = new int[N][20];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 20; j++)
                dp[i][j] = 0;
        }
 
        for (int j = 0; j < U.size(); j++) {
            for (int i = 0; i < 20; i++) {
                if ((U.get(j).get(2) & (1 << i)) != 0) {
                    dp[U.get(j).get(0) - 1][i]++;
                    if (U.get(j).get(1) < N)
                        dp[U.get(j).get(1)][i]--;
                }
            }
        }
 
        for (int j = 0; j < 20; j++) {
            for (int i = 1; i < N; i++) {
                dp[i][j] += dp[i - 1][j];
            }
        }
 
        for (int i = 0; i < N; i++) {
            int ansVal = 0;
            for (int j = 0; j < 20; j++) {
                if (dp[i][j] != 0)
                    ansVal += (1 << j);
            }
            a.set(i, ansVal);
        }
        return a;
    }
}

Python3

# Python3 code for the above approach:
 
def updateQuery(N, Q, U):
  # Code here
  a = [0]*N
  dp = [[0]*20 for i in range(N)]
  for j in range(len(U)):
      for i in range(20):
          if (U[j][2] & (1 << i)):
              dp[U[j][0] - 1][i] += 1
              if (U[j][1] < N):
                  dp[U[j][1]][i] -= 1
 
  for j in range(20):
      for i in range(1, N):
          dp[i][j] += dp[i - 1][j]
 
  for i in range(N):
      ans = 0
      for j in range(20):
          if (dp[i][j]):
              ans += (1 << j)
      a[i] = ans
 
  return a
 
# Drivers code
 
N = 3
Q = 2
U = [ [ 1, 2, 1 ], [ 3, 3, 2 ] ]
 
# Function Call
ans = updateQuery(N, Q, U)
for it in ans:
  print(it, end=" ")

C#

// C# code for the above approach:
 
using System;
using System.Collections.Generic;
 
class GFG {
    static List<int> UpdateQuery(int N, int Q,
                                 List<List<int> > U)
    {
        List<int> a = new List<int>(new int[N]);
        int[, ] dp = new int[N, 20];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 20; j++) {
                dp[i, j] = 0;
            }
        }
        for (int j = 0; j < U.Count; j++) {
            for (int i = 0; i < 20; i++) {
                if ((U[j][2] & (1 << i)) != 0) {
                    dp[U[j][0] - 1, i]++;
                    if (U[j][1] < N) {
                        dp[U[j][1], i]--;
                    }
                }
            }
        }
        for (int j = 0; j < 20; j++) {
            for (int i = 1; i < N; i++) {
                dp[i, j] += dp[i - 1, j];
            }
        }
        for (int i = 0; i < N; i++) {
            int ans = 0;
            for (int j = 0; j < 20; j++) {
                if (dp[i, j] != 0) {
                    ans += (1 << j);
                }
            }
            a[i] = ans;
        }
        return a;
    }
 
    static void Main(string[] args)
    {
        int N = 3, Q = 2;
        List<List<int> > U = new List<List<int> >();
        U.Add(new List<int>{ 1, 2, 1 });
        U.Add(new List<int>{ 3, 3, 2 });
 
        // Function Call
        List<int> ans = UpdateQuery(N, Q, U);
        foreach(var item in ans)
        {
            Console.Write(item + " ");
        }
    }
}

Javascript

// JavaScript code for the above approach:
 
function updateQuery(N, Q, U) {
  let a = new Array(N).fill(0);
  let dp = new Array(N);
  for (let i = 0; i < N; i++) {
    dp[i] = new Array(20).fill(0);
  }
  for (let j = 0; j < U.length; j++) {
    for (let i = 0; i < 20; i++) {
      if (U[j][2] & (1 << i)) {
        dp[U[j][0] - 1][i]++;
        if (U[j][1] < N) {
          dp[U[j][1]][i]--;
        }
      }
    }
  }
  for (let j = 0; j < 20; j++) {
    for (let i = 1; i < N; i++) {
      dp[i][j] += dp[i - 1][j];
    }
  }
  for (let i = 0; i < N; i++) {
    let ans = 0;
    for (let j = 0; j < 20; j++) {
      if (dp[i][j]) {
        ans += 1 << j;
      }
    }
    a[i] = ans;
  }
  return a;
}
 
// Example usage
let N = 3;
let Q = 2;
let U = [[1, 2, 1], [3, 3, 2]];
let ans = updateQuery(N, Q, U);
console.log(ans.join(" ")); // Outputs: 1 1 2

Output

1 1 2

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!