我们假设 pre[i]: 数组前i个数的之和，这就是前缀和
计算所有下标对 (1 <= l <= r <= n) pre[r] - pre[l] 之和
如果数据量是 n <= 1e5,直接两个for循环暴力求解的话，时间复杂度O(N^2),太慢了
暴力方法
点击查看代码
ll brute(){ll ans = 0;for(int l = 1;l<=n;l++){for(int r = l+1;r<=n;r++){ans += pre[r] - pre[l];}}return ans;
}
我们仔细观察，可以发现，
整个过程就是 :
ans += pre[i] - pre[j] (i固定,1 <= j < i),ans +=pre[j]-pre[i](i固定，i < j <= n)
通过这个式子,我们可以得到这个结论: -pre[i]出现了 n - i 次，+pre[i] 出现了 i - 1次
那么我们可以根据这个结论,遍历一遍数组,进行求和就好
时间复杂度为O(N)
点击查看代码
ll go(){ll ans = 0;for(int i = 1;i<=n;i++){// 这里可以整合成这样:ans += pre[i] * (2 * i - n - 1);ans += pre[i] * (i - 1); // +pre[i] 出现了 i - 1次ans -= pre[i] * (n - i); // -pre[i]出现了 n - i 次}return ans;
}
计算所有下标对 (1 <= l <= r <= n) |pre[r] - pre[l]| 之和
这里的||代表取绝对值
暴力方法
点击查看代码
ll brute(){ll ans = 0;for(int l = 1;l<=n;l++){for(int r = l+1;r<=n;r++){ans += std::abs(pre[r] - pre[l]);}}return ans;
}
如何优化呢？
我们再观察一下:
整个过程就是 :
ans += |pre[i] - pre[j]| (i固定,1 <= j < i),ans += |pre[j]-pre[i]| (i固定，i < j <= n)
根据绝对值的性质，如果pre[i] 比 pre[j]大，那么我们可以认为pre[j] 是减去的，pre[i]是加上的
否则就是pre[j] 是加上，pre[i]就是减去，结果和 |pre[i] - pre[j]| 是一样的
那么，在整个过程中，有多少个pre[i]是减去和以及多少个pre[i]是加上的呢？
我们可以先排序。
这样，大小关系就明确了，那么对于每一个pre[i]:
比pre[i]小的有 i - 1 个，也就意味着有 i - 1 个 pre[i] 应该加上
比pre[i]大的有 n - i 个，也就意味着有 n - i 个 pre[i] 应该减去
那么我们可以根据这个结论，去解决这个问题
时间复杂度为O(N* log N) ,因为排序时间复杂度是这个
点击查看代码
ll go(){ll ans = 0;std::sort(pre+1,pre+1+n);for(int i = 1;i<=n;i++){ans += pre[i] * (i - 1);ans -= pre[i] * (n - i);}return ans;
}
可以发现，这和上面那个求pre[r] - pre[l]总和代码是一样的，只是多了个排序而已。