Approach
For each query, the naive approach is to traverse the path from ‘a’ to ‘b’ and insert all the elements in the set. This can be simply achieved by using DFS Algorithm. The algorithm of this approach is given below:
Algorithm
-
Create a function dfs():
-
Function Description:
-
It takes ‘TREE’, ‘FROM’, ‘TO’, ‘PARENT’, ‘S’, ‘VALUE’, and ‘ANS’ as a parameter.
-
Function Working:
-
Insert the value of the ‘FROM’ node in the set ‘S’.
-
If FROM == To:
-
Iterate all the child nodes of the ‘FROM’ node:
-
If the child is not the parent, call dfs for its child.
-
Call the above function for all those queries whose first argument is ‘1’.
- Else update the value of that node.
Program
#include <bits/stdc++.h>
using namespace std;
/*Dfs Call*/
void dfs(vector<vector<int>> tree, int from, int to, int parent, set<int> s, vector<int> &value, int &ans)
{
/*Insert value of node.*/
s.insert(value[from]);
/*Base condition to terminate the recursive call.*/
if (from == to)
{
/* Assign answer*/
ans = s.size();
return;
}
for (int i = 0; i < tree[from].size(); i++)
{
/* If node is not a parent node*/
if (tree[from][i] != parent)
{
dfs(tree, tree[from][i], to, from, s, value, ans);
}
}
}
int main()
{
/*Taking number of nodes and queries as an input.*/
int n, q;
cin >> n >> q;
/*Creating tree.*/
vector<vector<int>> tree(n);
/*Assign value of node.*/
vector<int> value(n);
for (int i = 0; i < n; i++)
{
cin >> value[i];
}
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
while (q--)
{
set<int> s;
int a, b, c;
cin >> a >> b >> c;
if (a == 1)
{
int ans;
/*Funstion Call.*/
dfs(tree, b, c, -1, s, value, ans);
/*Print the answer.*/
cout << ans << endl;
}
else
{
/*Update the value.*/
value[b] = c;
}
}
return 0;
}
You can also try this code with Online C++ Compiler
Input
6 7
1 2 3 4 5 6
0 1
0 2
1 3
1 4
2 5
1 4 5
2 5 5
1 0 4
1 4 5
2 1 5
1 4 5
1 1 5
Output
5
3
4
3
3
Time Complexity
O(Q * N * log(N)), where ‘N’ is the number of elements in the array, and ‘Q’ is the total number of queries.
Reason: In the worst case, we have to traverse all the elements and in each traversal we need to insert its value in set which takes log(N) time.
Space Complexity
O(N), where N is the number of elements in the array.
Reason: Creating a set takes O(N) space in the worst case.
Check out Euclid GCD Algorithm
Frequently asked questions
-
What is a map?
The map is a data structure that stores data in key-value pairs. The map is of two types, i.e., ordered and unordered maps.
-
What is the difference between ordered and unordered sets?
The ordered set uses the concept of the red-black tree for its implementation, while the unordered set uses the concept of hashing.
-
What is the time complexity of the above code if we use an unordered set?
If we use an unordered set instead of an ordered set, its time complexity is O(N * Q). As insertion takes log(N) time in the ordered set and O(1) time in the unordered set.
-
What is the full form of DFS?
DFS stands for depth-first search. In this traversal, we go from the root of the tree to it's depth.
-
Can we solve the above problem in O(1) extra space?
Yes, we can, but time complexity increases in that implementation, as we need to traverse the whole array for all the elements.
Key Takeaways
In this blog, we learned about an interesting problem based on a range query. We solved the problem using the brute force approach. Another problem involving range query is: here.
Hence learning never stops, and there is a lot more to learn.
Check out this problem - Largest BST In Binary Tree
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
40+ registered 
