algorithm - 二维线段树更新/修改步骤复杂度

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从何而来？

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)，因为最终更新仅调用一次并且仅执行 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;

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