#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/polynomial-queries-pushdown

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/polynomial-queries-pushdown

Repovive

Polynomial Queries - Pushdown - Sqrt Decomposition | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Polynomial Queries - Pushdown

When tails need updates

For tail elements, you must "push down" lazy values before modifying individual elements.

function pushdown(block, arr, start, B)
    bStart := block * B
    for j from 0 to B - 1
        if bStart + j < n then
            arr[bStart + j] := arr[bStart + j] + start[block] + j
    start[block] := 0

Call $pushdown$ before processing tail elements in both updates and queries.

This adds $O(B) = O(\sqrt{n})$ per tail, maintaining overall $O(\sqrt{n})$ per operation.