区间和

这个区间和思想和之前的前缀和思想有相同之处，区别在于这个区间和是离散化的，在一个较大的区间中，多数元素为0，少部分有数据，求这部分区间和。

1. 首先取操作涉及的下标，即将要存数字的下标与求和范围两端的下标，存入小数组q中;
2. 对数组q排序;
3. 重新创建一个大小与q相同的数组s，从数组q中找到对应大数组要存入数据的位置映射，在s相同位置存入数据（q中找映射可以用二分法）;
4. 找大数组求和范围两端点在q中的映射位置，在数组s对应映射位置求和即可，可用前缀和.

   vector<int> alls; // 存储所有待离散化的值
   sort(alls.begin(), alls.end()); // 将所有值排序
   alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
   
   // 二分求出x对应的离散化的值
   int find(int x) // 找到第一个大于等于x的位置
   {
       int l = 0, r = alls.size() - 1;
       while (l < r)
       {
           int mid = l + r >> 1;
           if (alls[mid] >= x) r = mid;
           else l = mid + 1;
       }
       return r + 1; // 映射到1, 2, ...n
   }