我无法理解算法的asolution
尤其是，我不明白这部分代码是如何或者为什么
s += a[i];
total += query(s);
update(s);
允许您计算每个点左下象限中的点的总数。
有人能详细说明一下吗？
最佳答案
作为平面问题的模拟，请考虑：
对于位于（x，y）左下象限的点（a，b），a<
因此，形式（i，p[i]）的点位于左下象限
当i按升序迭代时，与当前点（i，P[i]）相比，先前考虑的所有点都位于左侧
所以我们只需要找到所有的P[j]s，小于到目前为止所考虑的P[i]
*当前点是指你引用的for循环的当前迭代中考虑的点，即（i，p[i]）
让我们定义另一个数组c[s]：
C[s] = Number of Prefix Sums of array A[1..(i - 1)] that amount to s
所以3的解变成了C[-2]+C[-1]+C[0]+C[1]+C[2]…C[P[i]-1，即C[P[i]]的前缀和
使用该位存储c的前缀和，从而将查询定义为：
query(s) = Number of Prefix Sums of array A[1..(i - 1)] that amount to a value < s
使用这些定义，给定代码中的s给出当前索引i（p[i]）的前缀和。total构建答案，update只需将p[i]添加到位。
我们必须对所有的i重复这个方法，因此for循环。
ps：它使用一种称为二叉索引树（http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees）的数据结构进行操作。如果你不知道，我建议你检查一下链接。
编辑：
给你一个数组s和一个值x，你可以把s分成两个不相交的子数组，这样l的所有元素都小于x，h的元素都大于或等于x。
A: All elements of L are less than all elements of H.
S的任何子序列T都有L的一些元素和H的一些元素。假设它有L的p元素和H的q元素。当T被排序为T'时，L的所有p元素都出现在H的q元素之前，因为A。
Median being the central value is the value at location m = (p + q)/2
直观地认为，q>=p意味着中值位于x，以此作为证明：
T'中位置[1..p]的值属于L。因此，若中值位于H，则其位置m应大于p：
m > p
(p + q)/2 > p
p + q > 2p
q > p
B: q - p > 0
对于计算机q-p，如果T'中的所有元素属于L（=X），则用+1替换
T看起来像{-1，-1，-11，1，1}
它有p乘以-1和q乘以1。T'的总和现在给我：
Sum = p * (-1) + q * (1)
C: Sum = q - p
我可以用这些信息在b中找到值。
所有子序列的形式都是{a[i]、a[i+2]、a[i+3]…A[J+1]}由于它们是连续的，为了计算A[I]到A[J+1]的和，我可以计算A[I]的前缀和，其中P[I]=A[1]+A[2]+。A[i-1]
从A[i]到A[j]的子序列之和可计算为P[j]-P[i]（j大于j和i）
考虑到C和B，我们得出结论：
Sum = P[j] - P[i] = q - p (q - p > 0)
P[j] - P[i] > 0
P[j] > P[i]
j>i和P[j]>P[i]对于每一个给出中值>=X的解
总而言之：
如果A[i]小于X，则用-1替换，否则用-1替换
A[i]的计算机前缀和
对于每对（i，p[i]），计算位于其左下象限的对。
关于algorithm - 计数左下象限中的点数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23707577/