Rust Solution | Beats 100% | Segment Tree
Approach
Build hashmap of actual position into index from left and right positions of every building.
For easy calculation, x inidx_to_x[idx] = xstands for[x, x
# Approach
- Build hashmap of actual position into index from left and right positions of every building.
- For easy calculation, x in `idx_to_x[idx] = x` stands for `[x, x + 1]` line segment.
- For every iteration over buildings:
    1. Query maximum height within range
    2. Update height to `side_length + max_height` for range
    3. Query maximum height for entire tree

# Complexity
- Time complexity: O(NlogN)
- Space complexity: O(N)

# Code
```rust []
use std::collections::HashMap;

struct SegmentTree {
    data: Vec<i32>,
}

impl SegmentTree {
    fn new(size: usize) -> Self {
        Self {
            data: vec![0; size],
        }
    }

    fn query(&self, node: usize, start: usize, end: usize, left: usize, right: usize) -> i32 {
        if left > end || right < start {
            return -1;
        }

        if left <= start && end <= right {
            return self.data[node];
        }

        let left_max = self.query(node * 2, start, (start + end) / 2, left, right);
        let right_max = self.query(node * 2 + 1, (start + end) / 2 + 1, end, left, right);

        left_max.max(right_max)
    }

    fn update(
        &mut self,
        node: usize,
        start: usize,
        end: usize,
        left: usize,
        right: usize,
        height: i32,
    ) {
        if left > end || right < start {
            return;
        }

        if start == end {
            self.data[node] = height;
            return;
        }

        self.update(node * 2, start, (start + end) / 2, left, right, height);
        self.update(
            node * 2 + 1,
            (start + end) / 2 + 1,
            end,
            left,
            right,
            height,
        );

        self.data[node] = self.data[node * 2].max(self.data[node * 2 + 1]);
    }
}

impl Solution {
    pub fn falling_squares(positions: Vec<Vec<i32>>) -> Vec<i32> {
        let mut idx_to_x = positions
            .iter()
            .flat_map(|x| [x[0], x[0] + x[1] - 1])
            .collect::<Vec<_>>();

        idx_to_x.sort();
        idx_to_x.dedup();

        let x_to_idx = idx_to_x
            .iter()
            .enumerate()
            .map(|(i, &x)| (x, i))
            .collect::<HashMap<_, _>>();

        let n = idx_to_x.len();

        let mut tree = SegmentTree::new(4 * n);
        let mut result = vec![];

        for position in positions {
            let (x, side_length) = (position[0], position[1]);
            let (left, right) = (x_to_idx[&x], x_to_idx[&(x + side_length - 1)]);

            let max_height = tree.query(1, 0, n - 1, left, right);

            tree.update(1, 0, n - 1, left, right, side_length + max_height);

            result.push(tree.query(1, 0, n - 1, 0, n - 1));
        }

        result
    }
}

```
['Segment Tree', 'Rust']