我要计算的一个数绝对差之和索引i与所有整数高达索引i-1 O（N）。但我没能想到的任何方式优于O（N ^ 2）。

有关如

  [3,5,6,7,1]
 

数组绝对值和必应（整数索引我总结会在索引我在另一个数组）：

  [0，2，4，7，17]
 

谁能帮助我减少复杂度为O（N）（如果不可能的，那么在时间复杂度方面至少有更好的优化）？

下面我的Python code：

  A = [3,5,6,7,1]
N = 5
absoluteSumArray = []
对于i在范围（0，n）的：
  总和= 0
  对于j在范围（0，i）的：
     总和+ = ABS（INT（A [1]） -  INT（A [J]））
  absoluteSumArray.append（和）
 

解决方案

我可以提供一个为O（n log n）的解决方案开始：设f 我的是第i个号码结果。我们有：

在通过阵列步行从左至右和维护元素的二叉搜索树的在 0 的到的在 I-1 的，我们可以解决的公式O的所有部件（log n）的：

在保持树的大小来计算的元素比小于给定一个大/小 在保持累加子树款项回答的总和查询元素大于/小于给定一个小

我们可以用一些简单的数据结构，更换增加搜索树，如果我们想避免实施成本：

排序数组事前。每一个分配数量的排名中的排序顺序 在随身携带一本二进制索引树的0/1值来计算比给定值小的元件的数目 保持数组值的另一个二进制索引树来计算比给定值小的元素之和

TBH我不认为这可以在O（N）在一般情况下得到解决。最起码，你需要的数字在一些点进行排序。但也许这些数字是有界的，也有一些其他的限制，所以你可能能够实现的总和并计算O操作（1）。

这是实现：

 ＃二进制索引树，使点更新和preFIX款项查询
类芬威克：
  高清__init __（个体经营，N）：
    self.tree = [0] *（N + 1）
    self.n = N
  高清update_point（自我，我，VAL）：＃O（log n）的
    I + = 1
    而I＆LT; = self.n：
      self.tree [I] + = VAL
      I + = I和-一世
  高清read_ preFIX（个体经营，I）：＃O（log n）的
    I + = 1
    总和= 0
    而I＆GT; 0：
      总和+ = self.tree [I]
      我 -  = I和-一世
    回报总和

高清解决（一）：
  等级= {V：我为I，V在枚举（排序（一））}
  RES = []
  计数，总和=芬威克（LEN（A）），芬威克（LEN（一））
  total_sum = 0
  对于I，X在历数（一）：
    R =等级[X]
    num_smaller = counts.read_ preFIX（R）
    sum_smaller = sums.read_ preFIX（R）
    res.append（total_sum  -  2 * sum_smaller + X *（2 * num_smaller  -  i））的
    counts.update_point（R，1）
    sums.update_point（R，X）
    total_sum + = X
  回报水库

打印（解决（[3,5,6,7,1]））＃[0，2，4，7，17]
打印（解决（[2,0,1]））＃[0，2，2]
 

I want to calculate the sum of absolute differences of a number at index i with all integers up to index i-1 in o(n). But i am not able to think of any approach better than o(n^2) .

For E.g. :

[3,5,6,7,1]

array with absolute sum will be(for integer at index i sum will be at index i in another array):

[0, 2, 4, 7, 17]

Can anyone help me to reduce the complexity to o(n) (if not possible then at least better optimization in terms of time complexity)?

Here my python code:

a=[3,5,6,7,1]
n=5
absoluteSumArray=[]
for i in range(0,n):
  Sum=0
  for j in range(0,i):
     Sum+=abs(int(a[i])-int(a[j]))
  absoluteSumArray.append(Sum)

解决方案

I can offer an O(n log n) solution for a start: Let fi be the i-th number of the result. We have:

When walking through the array from left to right and maintain a binary search tree of the elements a0 to ai-1, we can solve all parts of the formula in O(log n):

Keep subtree sizes to count the elements larger than/smaller than a given one Keep cumulative subtree sums to answer the sum queries for elements larger than/smaller than a given one

We can replace the augmented search tree with some simpler data structures if we want to avoid the implementation cost:

Sort the array beforehand. Assign every number its rank in the sorted order Keep a binary indexed tree of 0/1 values to calculate the number of elements smaller than a given value Keep another binary indexed tree of the array values to calculate the sums of elements smaller than a given value

TBH I don't think this can be solved in O(n) in the general case. At the very least you would need to sort the numbers at some point. But maybe the numbers are bounded or you have some other restriction, so you might be able to implement the sum and count operations in O(1).

An implementation:

# binary-indexed tree, allows point updates and prefix sum queries
class Fenwick:
  def __init__(self, n):
    self.tree = [0]*(n+1)
    self.n = n
  def update_point(self, i, val):  # O(log n)
    i += 1
    while i <= self.n:
      self.tree[i] += val
      i += i & -i
  def read_prefix(self, i):        # O(log n)
    i += 1
    sum = 0
    while i > 0:
      sum += self.tree[i]
      i -= i & -i
    return sum

def solve(a):
  rank = { v : i for i, v in enumerate(sorted(a)) }
  res = []
  counts, sums = Fenwick(len(a)), Fenwick(len(a))
  total_sum = 0
  for i, x in enumerate(a):
    r = rank[x]
    num_smaller = counts.read_prefix(r)
    sum_smaller = sums.read_prefix(r)
    res.append(total_sum - 2*sum_smaller + x * (2*num_smaller - i))
    counts.update_point(r, 1)
    sums.update_point(r, x)
    total_sum += x
  return res

print(solve([3,5,6,7,1]))  # [0, 2, 4, 7, 17]
print(solve([2,0,1]))      # [0, 2, 2]