2D segment tree update/modification step complexity

Check their update implementation

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]) 

Notice that at the end of the combination step it is iterating over all the columns of the array and updating all the items of the the corresponding tree. This is where the n comes from. But I would say that the complexity is O(n * log(m) + log(n), because final update is called only once and does only log(n)` changes

An implementation without the n factor

An implementation that only recalculates the nodes that depends on the changed element would have complexity O(log(n)*log(m)). This can be achieved by keeping track of the changed elements in the 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

The finalUpdate is a binary search and thus will be called log(m) recursion, each call changes one element, so changes will be 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 makes a binary search and will be called log(n) times, each call will re calculate log(m) nodes.