Counting Triangles in a Rectangular space using BIT

C++ Code

#include <bits/stdc++.h>
using namespace std;

// Initializing BIT
const int maxn = 2005;
int bit[maxn][maxn];

// Function to update BIT
void update(int x, int y){
    int y1;
    while(x < maxn){
        y1 = y;
        while(y1 < maxn){
            bit[x][y1]++;
            y1 += y1 & (-y1);
        }
        x += x & (-x);
    }
}

// Function to count points inside rectangle (1,1) and (x,y)
int query(int x, int y){
    int ans = 0;
    int y1;
    while (x > 0){
        y1 = y;
        while(y1 > 0){
            ans += bit[x][y1];
            y1 -= y1 & (-y1);
        }
        x -= x&(-x);
    }
    return ans;
}

// Function to count points inside rectangle (x1,y1) and (x2, y2)
int countPoints(int x1, int y1, int x2, int y2){
    return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}

// Function to count the number of triangles formed by n points
int countTriangles(int n){
    return (n*(n - 1) * (n - 2)) / 6;
}

// Driver code
int main(){
    vector<vector<int>> queries = {{2, 2}, {3, 5}, {4, 2}, {4, 5}, {5, 4}, {1, 1, 6, 6}, {3, 3}, {1, 1, 6, 6}};

    // Iterating over queries
    for (auto &i : queries){

        // Updating BIT for insert queries
        if (i.size() == 2){
            update(i[0], i[1]);
        }

        // Counting number of triangles
        else{
            int numPoints = countPoints(i[0], i[1], i[2], i[3]);
            int numTriangles = countTriangles(numPoints);

            // Printing number of triangles inside the rectangle
            cout<<numTriangles<<endl;
        }
    }
    return 0;
}

Output: 

10
20

Algorithm Complexity

Time Complexity: O(Q * log(MaxX) * log(MaxY))

We have implemented two functions for BIT:

update(): This function will insert a new point having coordinates (X, Y) in the plane in O(logX * logY) time.

query(): This function returns the number of points inside the rectangle in O(log(MaxX) log(MaxY)) time. Here, ‘MaxX’ and ‘MaxY’ denote the maximum X and Y coordinates of our plane.

We are either updating BIT for a single query or querying on BIT. Both these operations have O(logX * logY) complexity. After querying, the function to count the number of triangles takes constant time. So, for Q queries, the time complexity will be O(Q * log(MaxX) * log(MaxY))

Space Complexity: O(MaxX * MaxY) 

We have created a 2D bit, therefore the space complexity will be O(MaxX * MaxY) space where ‘MaxX’ and ‘MaxY’ denote the maximum X and Y coordinates of the 2D plane.

FAQs

1. What is a Binary Indexed Tree?
   A Binary Indexed Tree or Fenwick tree is a data structure that can efficiently update elements and calculate prefix sums of a list of numbers. It allows both the operations to be performed in time complexity of O(logN).
    
2. What is the difference between BIT and Segment Tree?
   A segment tree can be used to do a range query on any range L and R, but BIT can only be used for prefix queries, i.e., L is always equal to 1. BIT is more efficient than Segment Tree as it has a comparatively small constant factor.
    
3. How can we calculate the number of elements between 1 and X in an array for multiple queries? Given: Ai>=1.
   Note that the elements in the range 1 to X will form some prefix of an array. Our job is to count the number of elements in this prefix subarray. The efficient data structure to perform range operations on a prefix is Binary Indexed Tree (BIT). We can first store the frequency of each element in a separate array. Call this array ‘freq’. Now we just have to find the sum of freq[1] + freq[2]+ … + freq[X]. We can easily do it with BIT.
   We used this similar approach to count the number of points in the rectangle represented by coordinates (1,1) and (X, Y).

Key Takeaways

This article discussed how to count the number of triangles that can be formed by joining the points inside a given rectangle for multiple queries. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.
Check out this problem - Maximum Product Subarray

Until then, All the best for your future endeavors, and Keep Coding.