[c++] Fenwick tree - per query: O(log(roomSize) * log(roomsLength))
Build a fenwick tree,  the index of tree node represents it\'s min room size, and value is a set of possible room ids.\n\nSince the tree nodes are sparse, we ca
Build a [fenwick tree](https://cp-algorithms.com/data_structures/fenwick.html),  the index of tree node represents it\'s min room size, and value is a set of possible room ids.\n\nSince the tree nodes are sparse, we can use a hash map instead of an array for better efficiency.\n\nWhen answering a query,\n- we go through all the parent tree nodes (segments including the rooms with at least minRoomSize)\n\t- Time: ` O(log(roomSize))`. roomSize <= 1e7\n- and find the minimal possible id difference in each set of ids (binary search).\n\t- Time: `O(log(rooms.length)`). rooms.length <= 1e5\n\nSpace: `O(rooms.length*log(rooms.length))`\n\nNote a fenwick tree node aggregates indices from `0 ... i`. So to use a tree node to represent the `minRoomSize `, we can flip the range\nfrom `roomSize  ... MAX_ROOM_SIZE` to `0 ... (MAX_ROOM_SIZE - roomSize  + 1)`\n\n```cpp\nclass Solution {\n    int N;\n    unordered_map<int, set<int>> tree;\npublic:\n    void update(int n, int v) {\n        n = N - n + 1;\n        for (;n <= N; n += n & (-n)) tree[n].insert(v); \n    }\n    \n    int query(int n, int v) {\n        n = N - n + 1;\n        int res = -1, min_diff = INT_MAX, diff;\n        for (; n > 0; n -= n & (-n)) {\n            if (tree[n].size() == 0) continue;\n            auto itr = tree[n].lower_bound(v);\n            if (itr != tree[n].end()) {\n                diff = *itr - v;\n                if (diff < min_diff) res = *itr, min_diff = diff;\n                else if (diff == min_diff) res = min(res, *itr);\n            }\n            if (itr != tree[n].begin()) {\n                --itr;\n                diff = v - *itr;\n                if (diff < min_diff) res = *itr, min_diff = diff;\n                else if (diff == min_diff) res = min(res, *itr);\n            }\n        }\n        return res;\n    }\n    \n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {\n        N = 1e7;\n        for (auto &&r : rooms) update(r[1], r[0]);\n        \n        vector<int> res(queries.size());\n        for (int i = 0; i < queries.size(); ++i) {\n            res[i] = query(queries[i][1], queries[i][0]);\n        }\n        return res;\n    }\n};\n```
['Tree', 'C', 'Binary Tree']