Approach
Naive:
A simple approach would be to run DFS Algorithm from the node given in the query and count the number of nodes with values smaller than ‘val’. And this should be done for all queries. Therefore the time complexity of this solution would be O(Q * N).
However, we can optimize this complexity. Here the time complexity of DFS is O(N) which is the bottleneck in this approach.
Efficient/Optimized:
For improving the time complexity, we will reduce the problem of finding the nodes in a sub-tree to finding them in contiguous segments of an array.
We will use Euler Tour to generate such a representation. Euler tour is basically flattening of the tree. It is created by pushing nodes into an array when entering a subtree and exiting a subtree. Since we are pushing every node twice, the Euler tour contains twice the number of nodes. The property of this representation is that it contains a subtree of node X between the first and last occurrence of X in the Euler tour array. Therefore, counting the number of nodes that are smaller than ‘val’ between the first and last occurrence of ‘node’ (in the Euler tour array) will give us twice the answer of that query.
Counting nodes between the first and last occurrence of ‘node’ can be done efficiently using Binary Indexed Tree. Through the below steps:
1. Store the nodes from the Euler tour and their position in the array as (indexInTree, indexInTour). Then sort according to the indexInTree (Call this vector of pairs as sortedTour).
2. Similarly, store the queries in a vector of pairs in the form (val, node) and sort it according to val (Call this vector as sortedQuery).
3. Create two arrays, start[ ] and end[ ] using the Euler tour array. Here, start[X] represents the index of X’s first occurrence in the Euler tour, and similarly, end[X] means the last occurrence of X.
4. Create a Binary Indexed Tree of the length of size 2*N+1 and initialize it with 0s.
5. Now follow a two-pointer approach. Maintain two pointers, one in sortedTour and one in sortedQuery, and do the following:
a) For each query in sortedQuery of the form {val, node} we select a pairs from sortedTour whose indexInTree >= val. Then answer would be counted from start[node] to end[node] (which is calculated using Binary Indexed Tree). Then increment queryPtr.
b) If no such pair is available in sortedTour, we increment/update the count of the current pair (which is of the form {indexInTree, indexInTour}) in the Binary Indexed Tree and then increment tourPtr.
6) Above process is repeated until we find answers for all the queries.
Algorithm
1. Calculate/find Euler tour of the given tree. Store it in the array tour.
2. Create start & end arrays using Euler’s Tour array.
3. Create sortedTour & sortedQuery (As described in the approach section).
4. Find the answer for all queries using the two-pointer approach (Also described in the approach section).
Program
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
/*--------------- BINARY INDEXED TREE. //BEGINS -----------*/
vector<int>BIT;
/**
* @brief This is a utility function which calculate
* the sum of array[0 ... idx] using BIT data structure.
*
* @param idx Index tree node.
* @return int
*/
int Sum(int idx){
int _sum = 0;
/* Traversing the ancestors of idx node. */
while(idx > 0){
_sum += BIT[idx]; // Add current element in count.
idx -= (idx & -idx); // Move to 'sum' parent node.
}
// Return count of smaller element on the right side.
return _sum;
}
/**
* @brief This function updates a node of Binary Indexed Tree(BIT)
* at given index 'idx'. Given value 'change' is added to BIT[idx] node
* and its ancestors.
*
* @param idx Index tree node.
* @param change Effective difference that needs to be updated.
* @return void
*/
void Update(int idx, int change){
/* Traverse over all ancestors of BIT[idx] and add 'change' */
while(idx < BIT.size()){
BIT[idx] += change; // Add 'change' in current node.
idx += (idx & -idx); // Move to 'update' parent node.
}
}
/*--------------- BINARY INDEXED TREE. //ENDS -----------*/
// Adjacency list.
vector<vector<int>>adj;
/**
* @brief This function generates an Euler tour for a given tree.
* Euler tour flattens the tree structure.
*
* @param vis boolean array to keep track of visited nodes.
* @param tour array to store Euler tour.
* @param root Root node.
* @return void
*/
void makeEulerTour(vector<int> &vis, vector<int> &tour, int root){
// Node is pushed while entering a subtree.
tour.push_back(root);
vis[root] = 1;
for(auto v: adj[root]){
if(!vis[v]){
makeEulerTour(vis, tour, v);
}
}
// Node is pushed while exiting a subtree.
tour.push_back(root);
}
/**
* @brief Utility function to for creating start & end array.
*
* @param tour Array containing Euler’s tour
* @param start Start[x] stores first occurrence of node 'x' in tour
* @param end End[x] stores last occurrence of node 'x' in tour
*/
void fillStartEnd(vector<int> tour, vector<int> &start, vector<int> &end){
for(int i=1; i<tour.size(); i++){
if(start[tour[i]] == -1){
start[tour[i]] = i;
}else{
end[tour[i]] = i;
}
}
}
/**
* @brief This function returns sorted array of pairs
* containing {node, tourIndex}.
*
* @param tour
* @return vector<pii>
*/
vector<pii> createSortedTour(vector<int> &tour){
vector<pii> a;
for (int i = 1; i < tour.size(); ++i) {
a.push_back(make_pair(tour[i], i));
}
sort(a.begin(), a.end());
return a;
}
void solve(int N, vector<pii> queries){
// Reset BIT before solve a test case.
BIT.clear();
BIT.resize(2*N+4, 0);
// Declaring tour and some other useful vector.
vector<int> tour, vis(N+1, 0), start(N+1, -1), end(N+1, -1);
/* Inserting dummy element so to make it one based index. */
tour.push_back(-1);
// Make Euler Tour
makeEulerTour(vis, tour, 1);
// Pre-process start and end array with the help of tour array.
fillStartEnd(tour, start, end);
// Making sortedTour and sortedQuery
vector<pii> sortedTour = createSortedTour(tour);
vector<pii> sortedQuery = queries;
sort(sortedQuery.begin(), sortedQuery.end());
// For storing final answers.
map<pii, int> queryAns;
/* We keep a pointer for sortedTour and sortedQuery.
For each element X {node, tourIndex} in sortedTour, we first
process all queries will 'val' smaller than X's node and update
queryptr to first unprocessed query. */
int tourPtr=0, queryPtr=0;
while(queryPtr < sortedQuery.size()){
// sortedTour[tourPtr] stores {node, tourIndex}
// sortedQuery[queryPtr] stores {val, node}
// If sortedQuery[queryPtr].val <= sortedTour[tourPtr].node
while(queryPtr < sortedQuery.size() && sortedQuery[queryPtr].F <= sortedTour[tourPtr].F){
int node = sortedQuery[queryPtr].S;
// Find the count of nodes from start[node] -- end[node] in euler tour using BIT function.
queryAns[sortedQuery[queryPtr]] = ( Sum(end[node]) - Sum(start[node]-1) )/2;
queryPtr++;
}
if(tourPtr < sortedTour.size()){
Update(sortedTour[tourPtr].S, 1);
tourPtr++;
}
}
for(auto p: queries){
cout << "Count for {val " << p.F << ", node "<< p.S << "}: "<< queryAns[p] << endl;
}
}
// Driver Function.
int main(){
int tt; cin >> tt;
while(tt--){
int N, E; cin >> N >> E;
adj.clear();
adj = vector<vector<int>>(N+1);
for(int i=0; i<E; i++){
int u,v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int Q; cin >> Q;
vector<pii>queries;
for(int i=0; i<Q; i++){
int val, node; cin >> val >> node;
queries.push_back({val, node});
}
solve(N, queries);
}
return 0;
}
INPUT
1
7 6
1 4
1 6
4 2
4 3
4 5
6 7
4
4 1
7 6
5 1
4 4
OUTPUT
Count for {val 4, node 1}: 3
Count for {val 7, node 6}: 1
Count for {val 5, node 1}: 4
Count for {val 4, node 4}: 2
Time Complexity
The time complexity of the above approach is O(Q * log(N)).
Space Complexity
The auxiliary space complexity of the program is O(N * max{DegreeofNode}) (space taken by the adjacency list is the bottleneck).
Check out this array problem - Merge 2 Sorted Arrays
FAQs
-
What is Fenwick Tree or Binary Indexed Tree?
A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties).
-
What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
-
What is the advantage of Fenwick tree over Segment tree?
The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
-
What is the disadvantage of the Fenwick tree over the Segment tree?
We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.
Key Takeaways
Cheers if you reached here!!
This article discussed an intriguing problem using the Fenwick Tree or Binary Indexed Tree. Fenwick Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.
Yet learning never stops, and there is a lot more to learn. 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 Learning!!
306+ registered