题目链接：https://leetcode.cn/problems/rank-from-stream-lcci/

解题思路

这道题目的官方提示是使用一个携带额外信息的二叉搜索树来解决问题，用二叉搜索树的优点是对于输入数据的范围没有限制，但是缺点在于：如果使用朴素的二叉搜索树，最坏时间复杂度会很差，而平衡二叉搜索树的实现会比较复杂。考虑到题目中x的范围是[0, 5e4]，我们也可以使用树状数组来解决问题。

树状数组

树状数组（Binary Indexed Tree），也叫Fenwick Tree，是一种数据结构，可以用来高效地维护一个固定长度数组（设长度为N）的区间和。它支持两种操作：