algorithm - 2D 线段树更新/修改步骤复杂度

Question

我无法理解https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/中“修改查询”的复杂性。它在文章底部声明复杂度为 O(2 * n * log n * log m)。为什么不只是 O(log n * log m)？额外的线性项 n 是从哪里来的？

标签： algorithmtime-complexity

Answer 1

检查他们的更新实施

def update(pos, low, high, x, y, val): 
  
    if (low == high) : 
        finalUpdate(1, 1, 4, x, val, pos) 
      
    else : 
        mid = (low + high) // 2
  
        if (low <= y and y <= mid) : 
            update(2 * pos, low, mid, x, y, val) 
  
        else : 
            update(2 * pos + 1, mid + 1,  
                       high, x, y, val) 
  
        for i in range(1, size): 
            fin_seg[pos][i] = (fin_seg[2 * pos][i] +
                               fin_seg[2 * pos + 1][i]) 

请注意，在组合步骤结束时，它遍历数组的所有列并更新相应树的所有项。这就是它的n来源。但我会说复杂度是 O(n * log(m) + log(n) , because final update is called only once and does only log(n)` 变化

没有n因素的实现

仅重新计算依赖于已更改元素的节点的实现将具有复杂性O(log(n)*log(m))。这可以通过跟踪finalUpdate.

def finalUpdate(pos, low, high, x, val, node): 
    if (low == high) : 
        fin_seg[node][pos] = val 
        return [pos]
    else : 
        mid = (low + high) // 2
  
        if (low <= x and x <= mid) : 
            changes = finalUpdate(2 * pos, low, mid,  
                            x, val, node) 
          
        else : 
            changes = finalUpdate(2 * pos + 1, mid + 1,  
                            high, x, val, node) 
  
        changes.append(pos);
        fin_seg[node][pos] = (fin_seg[node][2 * pos] + 
                              fin_seg[node][2 * pos + 1]) 
        return changes

这finalUpdate是一种二分搜索，因此称为log(m)递归，每次调用都会更改一个元素，因此更改将是 log(m)。

def update(pos, low, high, x, y, val): 
  
    if (low == high) : 
        changes = finalUpdate(1, 1, 4, x, val, pos) 
      
    else : 
        mid = (low + high) // 2
  
        if (low <= y and y <= mid) : 
            changes = update(2 * pos, low, mid, x, y, val) 
  
        else : 
            changes = update(2 * pos + 1, mid + 1,  
                       high, x, y, val) 
  
        for i in changes: 
            fin_seg[pos][i] = (fin_seg[2 * pos][i] +
                               fin_seg[2 * pos + 1][i]) 
    return changes;

更新进行二分查找并被调用log(n)次数，每次调用都会重新计算log(m)节点。