算法：小于当前数字之和

一、背景

今天周六，leetcode 举办了 LCP 2020 团队赛。

我准备比赛的时候，发现账号没登录。
之后尝试登录的时候，发现无法登录，也没有任何错误提示，就是登录后还是提示登录。

没办法，只能放弃比赛了。

前几天一个朋友问我一道算法题，我看后说使用树状数组或线段树即可。

可能有点抽象吧，他说让我写成题解，那我就把这道题分享出来吧。

二、算法题

题目如上图，给一个数组，求每个位置前面小于该数字的值之和。

暴力做法是求循环求每个位置的答案。
复杂度是 O(n^2)。

那我们能不能快速求出一个位置前面小于该数字的和呢？

假设我们维护的有一个数据结构，可以快速求出小于一个数字的和，是不是就行了吗？
前面的数字假设已经排序了，那是不是就是求区间和了？

但是有个问题，后面会不断的插入新的数字，我们还需要维护区间和。

这不就是经典的平衡树吗？
平衡树天然可以插入数字，天然存在区间和。

但是自己维护一个平衡树难度比较高，有没有替代方案呢？

没错，假设数组的数字都在一个范围内，可以使用线段树来做。

比如第一个数字是 5， 我们只需要给第 5 个位置加上 5。
第二个数字是 4，我们就给第 4 个数字加上 4。
这样询问的时候，就是求区间和。

如果给的数字很大呢？
我们需要先预处理，排序，进行离散化。

什么是离散化呢？
就是对所有值从小到大进行索引编号，通过操作索引编号来操作值。

之前曾分享过很多离散化的算法题，比如这篇《任务调度（离散化版本）》，或者这篇《Leecode 第88场比赛回顾》。

离散化+线段树就可以完美解决这道题了。

之前如果你经常看我的题解的话，会发现我经常提起线段树，但是没有写过线段树。

为啥？
因为我都是使用树状数组代替了。
比如这篇《leetcode 第184算法比赛》。

没错，这次也可以使用树状数组来代替线段树。

假设这道题每个值都在 1W 以内，那就是裸的树状数字题了。

上图就是树状数组的全部代码，而我们要做的也很简单，伪代码如下。

vector<int> ans;
BITree biTree;
biTree.init(maxVal+1);
for(auto v: vec){
  biTree.modify(v, v);  
  ans.push_back(biTree.getsum(v-1));
}
return ans;

三、最后

树状数组与线段树是一种很强大的算法，可以解决不少问题，你学会了吗？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code