Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem
1.2.
Example -
2.
Approach
3.
C++ Code
4.
Algorithm Complexity
4.1.
Time Complexity: O(Q * log(MaxX) * log(MaxY))
4.2.
Space Complexity: O(MaxX * MaxY)
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Counting Triangles in a Rectangular space using BIT

## Introduction

#### Problem

In this problem, we are given a 2D plane and we have to perform two types of queries:

1. (x,y) - For this type of query, insert a point with coordinates (x,y) into the 2D plane.
2. (x1, y1, x2, y2) - For this type of query, first consider a rectangle having coordinates - (x1,y1), (x1,y2), (x2,y1), (x2,y2). Now count the number of triangles that can be formed by joining the points inside this rectangle. Also include the triangles with 0 areas in your answer.

In other words, we have to implement two types of queries. One is to insert a point in the plane, and the other is to count the number of triangles that can be formed inside a given rectangle.

#### Example -

Input: queries = [ {2, 2}, {3, 5}, {4, 2}, {4, 5}, {5, 4}, {1, 1, 6, 6} ].

Output: 10 20

Explanation:

1. In the first 5 queries, we have inserted 5 points in our 2D plane.
2. For the next query, we have to count the number of triangles formed by the points inside the rectangle (1,1),(1,6),(6,6),(6,1).

The plane will now look like this:

There are 5 points inside the given rectangle. To form a triangle, we can choose any 3 points and connect them. Therefore, the answer will be 5C3 = 10.

## Approach

First, let us assume that we know the number of points inside a rectangle at any instance. Let the number of points inside the given rectangle be ‘m’. Now, how can we count the number of triangles formed by these points?

The number of triangles formed by ‘m’ points is equal to mC3. Note that we will get a count of the triangles having non-zero areas and zero areas. As we have to count both, this will work.

We just need to find the number of points inside the given rectangle to count the number of triangles. Let P(x, y) define the number of points in a rectangle starting from (1,1) to (x, y). Thus, the number of points inside the rectangle defined by (x1, y1) and (x2, y2) will be:

``P(x2, y2) - P(x1-1, y2) - P(x2, y1-1) + P(x1-1, y1-1)``

We now need a way to find P(x,y). If we have to insert all the points at first and then count the number of triangles, then we can just maintain a 2D table to store the number of points such that ‘table[x][y]’ will store the number of points inside the rectangle defined by (1,1) and (x,y).

For multiple queries, we can use a 2D Binary Indexed Tree to insert a point and calculate P(x,y). The update function will add a new point in the table and the query function will return the number of points inside a rectangle, which will then be used to count the number of triangles inside that rectangle.

Also see, Euclid GCD Algorithm

## C++ Code

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.

Live masterclass