<p>You are given a <strong>0-indexed</strong> 2D integer array <code>flowers</code>, where <code>flowers[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> means the <code>i<sup>th</sup></code> flower will be in <strong>full bloom</strong> from <code>start<sub>i</sub></code> to <code>end<sub>i</sub></code> (<strong>inclusive</strong>). You are also given a <strong>0-indexed</strong> integer array <code>people</code> of size <code>n</code>, where <code>people[i]</code> is the time that the <code>i<sup>th</sup></code> person will arrive to see the flowers.</p>

<p>Return <em>an integer array </em><code>answer</code><em> of size </em><code>n</code><em>, where </em><code>answer[i]</code><em> is the <strong>number</strong> of flowers that are in full bloom when the </em><code>i<sup>th</sup></code><em> person arrives.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex1new.jpg" style="width: 550px; height: 216px;" />
<pre>
<strong>Input:</strong> flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
<strong>Output:</strong> [1,2,2,2]
<strong>Explanation: </strong>The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex2new.jpg" style="width: 450px; height: 195px;" />
<pre>
<strong>Input:</strong> flowers = [[1,10],[3,3]], people = [3,3,2]
<strong>Output:</strong> [2,2,1]
<strong>Explanation:</strong> The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= flowers.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>flowers[i].length == 2</code></li>
	<li><code>1 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= people.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= people[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class FenwickTree {
public:
    FenwickTree(int n) : n(n) {
        tree.resize(n + 1, 0);
    }

    // Function to update the tree with value 'val' at index 'i'
    void update(int i, int val) {
        while (i <= n) {
            tree[i] += val;
            i += i & -i;
        }
    }

    // Function to perform range update from l to r with value 'val'
    void rangeUpdate(int l, int r, int val) {
        update(l, val);
        update(r + 1, -val);
    }

    // Function to get the prefix sum from 1 to i
    int query(int i) const {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i;
        }
        return sum;
    }

private:
    vector<int> tree;
    int n;
};

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        vector<int> allTimes;
        
        // Collect all unique times from flowers and people
        for (const auto& flower : flowers) {
            allTimes.push_back(flower[0]);
            allTimes.push_back(flower[1]);
        }
        for (const auto& person : people) {
            allTimes.push_back(person);
        }

        // Sort and remove duplicates
        sort(allTimes.begin(), allTimes.end());
        allTimes.erase(unique(allTimes.begin(), allTimes.end()), allTimes.end());

        // Map each unique time to a compressed index
        unordered_map<int, int> timeToIndex;
        for (int i = 0; i < allTimes.size(); ++i) {
            timeToIndex[allTimes[i]] = i + 1;
        }

        FenwickTree fenwickTree(allTimes.size());

        // Perform range updates using compressed indices
        for (const auto& flower : flowers) {
            int start = timeToIndex[flower[0]];
            int end = timeToIndex[flower[1]];
            fenwickTree.rangeUpdate(start, end, 1);
        }

        vector<int> ans;
        for (const auto& person : people) {
            int index = timeToIndex[person];
            ans.push_back(fenwickTree.query(index));
        }
        return ans;
    }
};

105491