# Rectangle Area II
**Difficulty:** HARD
[External](https://leetcode.com/problems/rectangle-area-ii)
Canonical: https://scaleengineer.com/dsa/problems/rectangle-area-ii
**Patterns:** [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Data structures:** Array, Segment Tree, Ordered Set
---
## Problem
You are given a 2D array of axis-aligned `rectangles`. Each `rectangle[i] = [xi1, yi1, xi2, yi2]` denotes the `ith` rectangle where `(xi1, yi1)` are the coordinates of the **bottom-left corner**, and `(xi2, yi2)` are the coordinates of the **top-right corner**.

Calculate the **total area** covered by all `rectangles` in the plane. Any area covered by two or more rectangles should only be counted **once**.

Return _the **total area**_. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/rectangle-area-ii/image0.png) 

**Input:** rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
**Output:** 6
**Explanation:** A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

**Example 2:**

**Input:** rectangles = [[0,0,1000000000,1000000000]]
**Output:** 49
**Explanation:** The answer is 1018 modulo (109 + 7), which is 49.

**Constraints:**

* `1 <= rectangles.length <= 200`
* `rectanges[i].length == 4`
* `0 <= xi1, yi1, xi2, yi2 <= 109`
* `xi1 <= xi2`
* `yi1 <= yi2`
* All rectangles have non zero area.

# Approaches
## Grid Discretization
This approach involves discretizing the plane into a grid based on the unique x and y coordinates of the input rectangles. We then determine which cells of this grid are covered by at least one rectangle. The total area is the sum of the areas of all covered cells.
**Time:** O(N^3), where N is the number of rectangles. Collecting and sorting coordinates takes O(N log N). The main work is filling the grid, which involves iterating through N rectangles, and for each, iterating through a grid portion that can be up to O(N^2) in size. This results in an O(N^3) complexity. Summing the area takes O(N^2). · **Space:** O(N^2), where N is the number of rectangles. We store up to 2N unique x-coordinates and 2N unique y-coordinates, leading to a grid of size up to (2N) x (2N).
**Pros:** Conceptually straightforward and easy to understand.; Relatively simple to implement.
**Cons:** High time complexity of O(N^3), which might be too slow for larger constraints.; High space complexity of O(N^2) to store the grid.
### Explanation
The core idea is to break down the problem from a continuous plane to a discrete grid. The boundaries of this grid are defined by the x and y coordinates of all the given rectangles. 

First, we collect all unique x-coordinates (both `x1` and `x2`) and all unique y-coordinates (`y1` and `y2`) from the rectangles. We sort these unique coordinates to form two lists, `x_coords` and `y_coords`. These lists define the grid lines.

Next, we can create a 2D boolean array, say `covered_grid`, where `covered_grid[i][j]` corresponds to the elementary rectangle defined by corners `(x_coords[j], y_coords[i])` and `(x_coords[j+1], y_coords[i+1])`. We iterate through each input rectangle and for each one, we find the range of indices in `x_coords` and `y_coords` it spans. We then mark all the cells in `covered_grid` within this range as `true`.

Finally, we iterate through the `covered_grid`. For each cell `(i, j)` that is marked `true`, we calculate its area and add it to a running total. The area of cell `(i, j)` is `(x_coords[j+1] - x_coords[j]) * (y_coords[i+1] - y_coords[i])`. Since the total area can be very large, all calculations are performed using `long` and the sum is taken modulo `10^9 + 7`.

```java
import java.util.*;

class Solution {
    public int rectangleArea(int[][] rectangles) {
        int MOD = 1_000_000_007;
        
        Set<Integer> xSet = new TreeSet<>();
        Set<Integer> ySet = new TreeSet<>();
        
        for (int[] rect : rectangles) {
            xSet.add(rect[0]);
            xSet.add(rect[2]);
            ySet.add(rect[1]);
            ySet.add(rect[3]);
        }
        
        List<Integer> xCoords = new ArrayList<>(xSet);
        List<Integer> yCoords = new ArrayList<>(ySet);
        
        Map<Integer, Integer> xMap = new HashMap<>();
        for (int i = 0; i < xCoords.size(); i++) {
            xMap.put(xCoords.get(i), i);
        }
        
        Map<Integer, Integer> yMap = new HashMap<>();
        for (int i = 0; i < yCoords.size(); i++) {
            yMap.put(yCoords.get(i), i);
        }
        
        boolean[][] grid = new boolean[yCoords.size()][xCoords.size()];
        
        for (int[] rect : rectangles) {
            int x1 = xMap.get(rect[0]);
            int x2 = xMap.get(rect[2]);
            int y1 = yMap.get(rect[1]);
            int y2 = yMap.get(rect[3]);
            
            for (int i = y1; i < y2; i++) {
                for (int j = x1; j < x2; j++) {
                    grid[i][j] = true;
                }
            }
        }
        
        long totalArea = 0;
        for (int i = 0; i < yCoords.size() - 1; i++) {
            for (int j = 0; j < xCoords.size() - 1; j++) {
                if (grid[i][j]) {
                    long width = xCoords.get(j + 1) - xCoords.get(j);
                    long height = yCoords.get(i + 1) - yCoords.get(i);
                    totalArea = (totalArea + (width * height)) % MOD;
                }
            }
        }
        
        return (int) totalArea;
    }
}
```
### Algorithm
- Create two sorted lists of unique coordinates, one for all x-coordinates (`x_coords`) and one for all y-coordinates (`y_coords`) from the input rectangles.
- These sorted coordinates define a grid. An elementary rectangle (a cell in the grid) is formed by `(x_coords[j], y_coords[i])` and `(x_coords[j+1], y_coords[i+1])`.
- Create a 2D boolean array `grid` with dimensions `(number of unique y's) x (number of unique x's)` to keep track of which elementary rectangles are covered.
- For each input rectangle, iterate through the elementary rectangles it covers and mark the corresponding entry in the `grid` as `true`.
- Initialize `total_area = 0`.
- Iterate through the `grid`. If `grid[i][j]` is `true`, calculate the area of the corresponding elementary rectangle: `width = x_coords[j+1] - x_coords[j]` and `height = y_coords[i+1] - y_coords[i]`. 
- Add the product `(width * height)` to `total_area`, taking the result modulo `10^9 + 7` at each step.
- Return the final `total_area`.

## Plane Sweep Algorithm
A more efficient method is the Plane Sweep or Sweep-Line algorithm. We imagine a vertical line sweeping across the plane from left to right. The total area is computed by summing up the areas of thin vertical strips. The algorithm processes events (rectangles starting or ending) at each distinct x-coordinate.
**Time:** O(N^2 log N). Sorting the 2N events takes O(N log N). The sweep-line processes O(N) distinct x-coordinates. At each step, calculating the merged length of active intervals involves sorting them, which takes O(N log N). This leads to a total complexity of O(N * N log N) = O(N^2 log N). · **Space:** O(N), where N is the number of rectangles. We store 2N events and at most N active y-intervals.
**Pros:** Significantly better time complexity than the grid approach.; Lower space complexity, O(N), as we only need to store events and active intervals.
**Cons:** The process of calculating the union of active y-intervals at each step by sorting and merging is inefficient, leading to an overall complexity of O(N^2 log N).
### Explanation
The plane sweep algorithm works by calculating area incrementally. We consider a vertical sweep line that moves from left to right. The total area is the sum of areas of vertical strips between consecutive x-coordinates where something changes.

1.  **Events**: A change occurs at the left and right edges of each rectangle. We model these as events. For each rectangle `[x1, y1, x2, y2]`, we generate two events: `(x1, y1, y2, +1)` signifying the start of a rectangle, and `(x2, y1, y2, -1)` signifying the end. We collect all `2N` events.

2.  **Sorting**: We sort these events based on their x-coordinate. This gives us the sequence of positions for our sweep line.

3.  **Sweeping**: We iterate through the sorted events. Let's say we are moving from `last_x` to `current_x`. The width of this strip is `current_x - last_x`. In this strip, the set of active rectangles is constant. The height of the covered region in this strip is the length of the union of the y-intervals of all active rectangles.

4.  **Calculating Height**: To calculate this covered height, we maintain a list of active y-intervals. At each step, we can sort these intervals and merge them to find the total length. For example, if active intervals are `[0, 2]` and `[1, 3]`, their union is `[0, 3]` with length 3.

5.  **Updating State**: When the sweep line passes an event at `current_x`, we update our list of active intervals. For a start event, we add its y-interval. For an end event, we remove it. Then we update `last_x` to `current_x` and proceed to the next event.

This approach is more efficient than grid discretization, but the repeated sorting of active intervals is a bottleneck.

```java
import java.util.*;

class Solution {
    public int rectangleArea(int[][] rectangles) {
        int MOD = 1_000_000_007;
        List<int[]> events = new ArrayList<>();
        for (int[] rect : rectangles) {
            // event: [x, y1, y2, type], type 1 for start, -1 for end
            events.add(new int[]{rect[0], rect[1], rect[3], 1});
            events.add(new int[]{rect[2], rect[1], rect[3], -1});
        }

        Collections.sort(events, (a, b) -> a[0] - b[0]);

        long totalArea = 0;
        long lastX = events.get(0)[0];
        List<int[]> activeIntervals = new ArrayList<>();

        for (int i = 0; i < events.size(); ) {
            int currentX = events.get(i)[0];
            long width = currentX - lastX;

            if (width > 0) {
                long yLength = 0;
                if (!activeIntervals.isEmpty()) {
                    Collections.sort(activeIntervals, (a, b) -> a[0] - b[0]);
                    int start = activeIntervals.get(0)[0];
                    int end = activeIntervals.get(0)[1];
                    for (int j = 1; j < activeIntervals.size(); j++) {
                        int[] interval = activeIntervals.get(j);
                        if (interval[0] < end) {
                            end = Math.max(end, interval[1]);
                        } else {
                            yLength += (end - start);
                            start = interval[0];
                            end = interval[1];
                        }
                    }
                    yLength += (end - start);
                }
                totalArea = (totalArea + width * yLength) % MOD;
            }

            int temp_i = i;
            while (temp_i < events.size() && events.get(temp_i)[0] == currentX) {
                int[] event = events.get(temp_i);
                int[] interval = new int[]{event[1], event[2]};
                if (event[3] == 1) {
                    activeIntervals.add(interval);
                } else { // type == -1
                    // This removal is O(N)
                    for(int k=0; k<activeIntervals.size(); k++){
                        if(activeIntervals.get(k)[0] == interval[0] && activeIntervals.get(k)[1] == interval[1]){
                            activeIntervals.remove(k);
                            break;
                        }
                    }
                }
                temp_i++;
            }
            i = temp_i;
            lastX = currentX;
        }

        return (int) totalArea;
    }
}
```
### Algorithm
- For each rectangle `[x1, y1, x2, y2]`, create two events: an 'enter' event `(x1, y1, y2, 1)` and a 'leave' event `(x2, y1, y2, -1)`.
- Store all these events in a list and sort them primarily by their x-coordinate.
- Initialize `total_area = 0`, `last_x` to the x-coordinate of the first event, and an empty list `active_intervals` to store the y-intervals `[y1, y2]` of rectangles currently intersecting the sweep line.
- Iterate through the sorted events:
  - Let the current event's x-coordinate be `current_x`.
  - Calculate the width of the vertical strip: `width = current_x - last_x`.
  - If `width > 0`, calculate the total length of the union of `active_intervals`. This is done by sorting `active_intervals` and merging them to find the total covered length on the y-axis.
  - Add `(width * covered_length)` to `total_area` (modulo `10^9 + 7`).
  - Process all events at `current_x`: if it's an 'enter' event, add its y-interval to `active_intervals`; if it's a 'leave' event, remove it.
  - Update `last_x = current_x`.
- Return the final `total_area`.

## Plane Sweep with Segment Tree
This approach optimizes the plane sweep algorithm by using a Segment Tree to efficiently calculate the length of the union of vertical intervals. Instead of re-calculating the union from scratch at each step, the segment tree maintains this length and allows for efficient updates.
**Time:** O(N log N). Sorting events takes O(N log N). The sweep processes 2N events. Each event triggers a segment tree update, which takes O(log N) time (since the number of unique y-coordinates is at most 2N). The total time is dominated by sorting and the sweep, resulting in O(N log N). · **Space:** O(N), where N is the number of rectangles. We store 2N events, O(N) unique y-coordinates, and the segment tree requires O(N) space.
**Pros:** Optimal time complexity for this type of problem.; Efficiently handles the core challenge of calculating the union of intervals.
**Cons:** Implementation is more complex due to the Segment Tree data structure.
### Explanation
This is the most efficient approach, building upon the plane sweep algorithm. The bottleneck in the previous approach was calculating the total length of active y-intervals, which took O(N log N) time. We can optimize this calculation to O(log N) using a Segment Tree.

The setup is similar: we create 'enter' and 'leave' events and sort them by their x-coordinate. The key difference lies in how we manage the active y-intervals.

1.  **Y-Coordinate Discretization**: First, we collect all unique y-coordinates from the rectangles and sort them. Let this list be `y_coords`. The segment tree will be built upon the indices of this list. An interval `[y_coords[i], y_coords[i+1]]` is a basic segment.

2.  **Segment Tree Structure**: Each node in the segment tree will represent a range of y-intervals, e.g., `[y_coords[i], y_coords[j]]`. We store two values in each node:
    *   `count`: An integer representing how many rectangles currently cover this entire segment. An update for a rectangle `[y1, y2]` will affect the `count` of all segment tree nodes fully contained within the range from `y1` to `y2`.
    *   `length`: The total length of the covered portion within this node's range. 

3.  **Update and Query**: As we sweep from left to right:
    *   The area of a strip is `width * segment_tree_root.length`. The `length` at the root node gives the total covered length on the current sweep line.
    *   When we process an event `(x, y1, y2, type)`, we find the indices corresponding to `y1` and `y2` in our `y_coords` list. We then perform a range update on the segment tree for this index range. `type = +1` for 'enter' increases the `count`, and `type = -1` for 'leave' decreases it.
    *   After updating the `count` for a node, we update its `length`. If `node.count > 0`, the entire interval is covered, so `node.length` is the physical length of its y-range. If `node.count == 0`, its covered length is the sum of the lengths of its children.

This way, both querying the total length and updating the set of intervals take only O(log N) time, leading to a much faster overall algorithm.

```java
import java.util.*;

class Solution {
    public int rectangleArea(int[][] rectangles) {
        int MOD = 1_000_000_007;
        List<int[]> events = new ArrayList<>();
        TreeSet<Integer> ySet = new TreeSet<>();

        for (int[] r : rectangles) {
            events.add(new int[]{r[0], r[1], r[3], 1});
            events.add(new int[]{r[2], r[1], r[3], -1});
            ySet.add(r[1]);
            ySet.add(r[3]);
        }

        Collections.sort(events, (a, b) -> a[0] - b[0]);
        List<Integer> yCoords = new ArrayList<>(ySet);
        Map<Integer, Integer> yMap = new HashMap<>();
        for (int i = 0; i < yCoords.size(); i++) {
            yMap.put(yCoords.get(i), i);
        }

        int n = yCoords.size();
        long[] length = new long[4 * n];
        int[] count = new int[4 * n];

        long totalArea = 0;
        int lastX = events.get(0)[0];

        for (int i = 0; i < events.size(); i++) {
            int[] event = events.get(i);
            int curX = event[0];
            long width = curX - lastX;

            if (width > 0) {
                totalArea = (totalArea + width * length[1]) % MOD;
            }

            int y1_idx = yMap.get(event[1]);
            int y2_idx = yMap.get(event[2]);
            int type = event[3];

            update(1, 0, n - 1, y1_idx, y2_idx - 1, type, count, length, yCoords);
            lastX = curX;
        }

        return (int) totalArea;
    }

    private void update(int node, int start, int end, int l, int r, int val, int[] count, long[] length, List<Integer> yCoords) {
        if (start > r || end < l) {
            return;
        }
        if (l <= start && end <= r) {
            count[node] += val;
        } else {
            int mid = start + (end - start) / 2;
            update(2 * node, start, mid, l, r, val, count, length, yCoords);
            update(2 * node + 1, mid + 1, end, l, r, val, count, length, yCoords);
        }
        
        if (count[node] > 0) {
            length[node] = yCoords.get(end + 1) - yCoords.get(start);
        } else {
            if (start == end) {
                length[node] = 0;
            } else {
                length[node] = length[2 * node] + length[2 * node + 1];
            }
        }
    }
}
```
### Algorithm
- Collect all unique y-coordinates and sort them. This forms the basis for our segment tree.
- Create events `(x, y1, y2, type)` as in the previous approach and sort them by x-coordinate.
- Build a segment tree over the y-coordinate indices. Each node in the tree will store a `count` (how many active rectangles cover its interval) and a `length` (the total covered length within its interval).
- Initialize `total_area = 0` and `last_x`.
- Sweep through the sorted events:
  - For a strip between `last_x` and `current_x`, the width is `current_x - last_x`.
  - The covered height is the `length` value stored at the root of the segment tree.
  - Add `(width * root.length)` to `total_area`.
  - At `current_x`, process all events. For an 'enter' event, perform a range update on the segment tree to increment the `count` for its y-interval. For a 'leave' event, decrement the `count`.
  - After each update, recalculate the `length` in the affected segment tree nodes. A node's `length` is its full interval length if its `count > 0`; otherwise, it's the sum of its children's lengths.
- Return the final `total_area`.

# Solutions
### Java

```java
class Node { int l , r , cnt , length ; } class SegmentTree { private Node [] tr ; private int [] nums ; public SegmentTree ( int [] nums ) { this . nums = nums ; int n = nums . length - 1 ; tr = new Node [ n << 2 ]; for ( int i = 0 ; i < tr . length ; ++ i ) { tr [ i ] = new Node (); } build ( 1 , 0 , n - 1 ); } private void build ( int u , int l , int r ) { tr [ u ]. l = l ; tr [ u ]. r = r ; if ( l != r ) { int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); } } public void modify ( int u , int l , int r , int k ) { if ( tr [ u ]. l >= l && tr [ u ]. r <= r ) { tr [ u ]. cnt += k ; } else { int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; if ( l <= mid ) { modify ( u << 1 , l , r , k ); } if ( r > mid ) { modify ( u << 1 | 1 , l , r , k ); } } pushup ( u ); } private void pushup ( int u ) { if ( tr [ u ]. cnt > 0 ) { tr [ u ]. length = nums [ tr [ u ]. r + 1 ] - nums [ tr [ u ]. l ]; } else if ( tr [ u ]. l == tr [ u ]. r ) { tr [ u ]. length = 0 ; } else { tr [ u ]. length = tr [ u << 1 ]. length + tr [ u << 1 | 1 ]. length ; } } public int query () { return tr [ 1 ]. length ; } } class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int rectangleArea ( int [][] rectangles ) { int n = rectangles . length ; int [][] segs = new int [ n << 1 ][ 4 ]; int i = 0 ; TreeSet < Integer > ts = new TreeSet <>(); for ( var e : rectangles ) { int x1 = e [ 0 ], y1 = e [ 1 ], x2 = e [ 2 ], y2 = e [ 3 ]; segs [ i ++] = new int [] { x1 , y1 , y2 , 1 }; segs [ i ++] = new int [] { x2 , y1 , y2 , - 1 }; ts . add ( y1 ); ts . add ( y2 ); } Arrays . sort ( segs , ( a , b ) -> a [ 0 ] - b [ 0 ]); Map < Integer , Integer > m = new HashMap <>( ts . size ()); i = 0 ; int [] nums = new int [ ts . size ()]; for ( int v : ts ) { m . put ( v , i ); nums [ i ++] = v ; } SegmentTree tree = new SegmentTree ( nums ); long ans = 0 ; for ( i = 0 ; i < segs . length ; ++ i ) { var e = segs [ i ]; int x = e [ 0 ], y1 = e [ 1 ], y2 = e [ 2 ], k = e [ 3 ]; if ( i > 0 ) { ans += ( long ) tree . query () * ( x - segs [ i - 1 ][ 0 ]); } tree . modify ( 1 , m . get ( y1 ), m . get ( y2 ) - 1 , k ); } ans %= MOD ; return ( int ) ans ; } }
```

### CPP

```cpp
class Node { public: int l , r , cnt , length ; }; class SegmentTree { public: vector < Node *> tr ; vector < int > nums ; SegmentTree ( vector < int >& nums ) { this -> nums = nums ; int n = nums . size () - 1 ; tr . resize ( n << 2 ); for ( int i = 0 ; i < tr . size (); ++ i ) tr [ i ] = new Node (); build ( 1 , 0 , n - 1 ); } void build ( int u , int l , int r ) { tr [ u ] -> l = l ; tr [ u ] -> r = r ; if ( l != r ) { int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); } } void modify ( int u , int l , int r , int k ) { if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) tr [ u ] -> cnt += k ; else { int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( l <= mid ) modify ( u << 1 , l , r , k ); if ( r > mid ) modify ( u << 1 | 1 , l , r , k ); } pushup ( u ); } int query () { return tr [ 1 ] -> length ; } void pushup ( int u ) { if ( tr [ u ] -> cnt ) tr [ u ] -> length = nums [ tr [ u ] -> r + 1 ] - nums [ tr [ u ] -> l ]; else if ( tr [ u ] -> l == tr [ u ] -> r ) tr [ u ] -> length = 0 ; else tr [ u ] -> length = tr [ u << 1 ] -> length + tr [ u << 1 | 1 ] -> length ; } }; class Solution { public: const int mod = 1e9 + 7 ; int rectangleArea ( vector < vector < int >>& rectangles ) { int n = rectangles . size (); vector < vector < int >> segs ( n << 1 ); set < int > ts ; int i = 0 ; for ( auto & e : rectangles ) { int x1 = e [ 0 ], y1 = e [ 1 ], x2 = e [ 2 ], y2 = e [ 3 ]; segs [ i ++ ] = { x1 , y1 , y2 , 1 }; segs [ i ++ ] = { x2 , y1 , y2 , - 1 }; ts . insert ( y1 ); ts . insert ( y2 ); } sort ( segs . begin (), segs . end ()); unordered_map < int , int > m ; i = 0 ; for ( int v : ts ) m [ v ] = i ++ ; vector < int > nums ( ts . begin (), ts . end ()); SegmentTree * tree = new SegmentTree ( nums ); long long ans = 0 ; for ( int i = 0 ; i < segs . size (); ++ i ) { auto e = segs [ i ]; int x = e [ 0 ], y1 = e [ 1 ], y2 = e [ 2 ], k = e [ 3 ]; if ( i > 0 ) ans += ( long long ) tree -> query () * ( x - segs [ i - 1 ][ 0 ]); tree -> modify ( 1 , m [ y1 ], m [ y2 ] - 1 , k ); } ans %= mod ; return ( int ) ans ; } };
```

### Python

```python
class Node : def __init__ ( self ): self . l = self . r = 0 self . cnt = self . length = 0 class SegmentTree : def __init__ ( self , nums ): n = len ( nums ) - 1 self . nums = nums self . tr = [ Node () for _ in range ( n << 2 )] self . build ( 1 , 0 , n - 1 ) def build ( self , u , l , r ): self . tr [ u ]. l , self . tr [ u ]. r = l , r if l != r : mid = ( l + r ) >> 1 self . build ( u << 1 , l , mid ) self . build ( u << 1 | 1 , mid + 1 , r ) def modify ( self , u , l , r , k ): if self . tr [ u ]. l >= l and self . tr [ u ]. r <= r : self . tr [ u ]. cnt += k else : mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if l <= mid : self . modify ( u << 1 , l , r , k ) if r > mid : self . modify ( u << 1 | 1 , l , r , k ) self . pushup ( u ) def pushup ( self , u ): if self . tr [ u ]. cnt : self . tr [ u ]. length = self . nums [ self . tr [ u ]. r + 1 ] - self . nums [ self . tr [ u ]. l ] elif self . tr [ u ]. l == self . tr [ u ]. r : self . tr [ u ]. length = 0 else : self . tr [ u ]. length = self . tr [ u << 1 ]. length + self . tr [ u << 1 | 1 ]. length @ property def length ( self ): return self . tr [ 1 ]. length class Solution : def rectangleArea ( self , rectangles : List [ List [ int ]]) -> int : segs = [] alls = set () for x1 , y1 , x2 , y2 in rectangles : segs . append (( x1 , y1 , y2 , 1 )) segs . append (( x2 , y1 , y2 , - 1 )) alls . update ([ y1 , y2 ]) segs . sort () alls = sorted ( alls ) tree = SegmentTree ( alls ) m = { v : i for i , v in enumerate ( alls )} ans = 0 for i , ( x , y1 , y2 , k ) in enumerate ( segs ): if i : ans += tree . length * ( x - segs [ i - 1 ][ 0 ]) tree . modify ( 1 , m [ y1 ], m [ y2 ] - 1 , k ) ans %= int ( 1e9 + 7 ) return ans
```