Implementing Square Root Decomposition

1. Implementing Square Root Decomposition

Square Root Decomposition is a technique used to optimize range query operations on arrays. It divides the array into blocks of size approximately √n, allowing efficient updates and queries.

Component	Description	Implementation
Block Size	Size of each block, typically √n	`blockSize = Math.ceil(Math.sqrt(n))`
Number of Blocks	Total number of blocks	`numBlocks = Math.ceil(n / blockSize)`
Block Index	Block index for element at position i	`blockIndex = Math.floor(i / blockSize)`

Example: Basic Implementation

class SquareRootDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.numBlocks = Math.ceil(this.n / this.blockSize);
    this.blocks = new Array(this.numBlocks).fill(0);
    this.array = [...arr];

    // Initialize blocks with sum
    for (let i = 0; i < this.n; i++) {
      const blockIndex = Math.floor(i / this.blockSize);
      this.blocks[blockIndex] += this.array[i];
    }
  }

  update(index, value) {
    const blockIndex = Math.floor(index / this.blockSize);
    this.blocks[blockIndex] -= this.array[index];
    this.blocks[blockIndex] += value;
    this.array[index] = value;
  }

  rangeSum(left, right) {
    let sum = 0;
    let i = left;

    while (i <= right) {
      const blockIndex = Math.floor(i / this.blockSize);
      const blockStart = blockIndex * this.blockSize;
      const blockEnd = Math.min(blockStart + this.blockSize - 1, this.n - 1);

      if (i >= blockStart && right <= blockEnd) {
        // Entire range is within one block
        for (let j = i; j <= right; j++) {
          sum += this.array[j];
        }
        break;
      } else if (i >= blockStart) {
        // Start of range is within this block
        for (let j = i; j <= blockEnd; j++) {
          sum += this.array[j];
        }
        i = blockEnd + 1;
      } else {
        // Range starts before this block
        const end = Math.min(blockEnd, right);
        for (let j = blockStart; j <= end; j++) {
          sum += this.array[j];
        }
        i = end + 1;
      }
    }

    return sum;
  }
}

// Example usage:
const arr = [1, 2, 3, 4, 5, 6, 7, 8];
const srd = new SquareRootDecomposition(arr);
console.log(srd.rangeSum(1, 4)); // Output: 14 (2+3+4+5)
srd.update(2, 10);
console.log(srd.rangeSum(1, 4)); // Output: 21 (2+10+4+5)

Note: The Square Root Decomposition technique is particularly useful for problems where frequent range queries and updates are required. It provides a balance between query and update time complexities.

2. Dividing Array into Blocks

Block Size	Calculation	Notes
blockSize	`ceil(sqrt(n))`	Optimal block size for sqrt decomposition
numBlocks	`ceil(n / blockSize)`	Total number of blocks

Example: Calculating Block Size

// For an array of size 16
const n = 16;
const blockSize = Math.ceil(Math.sqrt(n)); // 4
const numBlocks = Math.ceil(n / blockSize); // 4

Note: Block size is typically ceil(sqrt(n)) to balance query and update times.

3. Implementing Range Sum Query

Example: Square Root Decomposition for Range Sum Query

class RangeSumQuery {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.blocks = new Array(this.blockSize).fill(0);
    
    for (let i = 0; i < this.n; i++) {
      this.blocks[Math.floor(i / this.blockSize)] += arr[i];
    }
  }

  query(left, right) {
    let sum = 0;
    let blockLeft = Math.floor(left / this.blockSize);
    let blockRight = Math.floor(right / this.blockSize);

    if (blockLeft === blockRight) {
      for (let i = left; i <= right; i++) {
        sum += arr[i];
      }
    } else {
      let i = left;
      while (i < (blockLeft + 1) * this.blockSize && i <= right) {
        sum += arr[i];
        i++;
      }

      for (let j = blockLeft + 1; j < blockRight; j++) {
        sum += this.blocks[j];
      }

      i = blockRight * this.blockSize;
      while (i <= right) {
        sum += arr[i];
        i++;
      }
    }

    return sum;
  }
}

Operation	Description	Time Complexity	Space Complexity
Preprocessing	Build blocks of size √n	`O(n)`	`O(√n)`
Range Sum Query	Sum elements from index `left` to `right`	`O(√n)`	`O(1)`

Note: The block size is chosen as ⌈√n⌉ to balance query and preprocessing time.

4. Implementing Range Update

Range updates in Square Root Decomposition involve updating a range of elements in the array efficiently. This is typically done by maintaining a separate lazy array to track pending updates.

Operation	Description	Time Complexity	Space Complexity
Update Range	Updates all elements in a given range [l, r] with a value.	O(√n)	O(√n)
Query Element	Retrieves the value of an element at a specific index.	O(1)	O(1)

Example: Range Update Implementation

class SquareRootDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.blocks = new Array(this.blockSize).fill(0);
    this.lazy = new Array(this.blockSize).fill(0);
    this.arr = [...arr];
  }

  updateRange(l, r, value) {
    const blockStart = Math.floor(l / this.blockSize);
    const blockEnd = Math.floor(r / this.blockSize);

    for (let i = blockStart; i <= blockEnd; i++) {
      const left = Math.max(l, i * this.blockSize);
      const right = Math.min(r, (i + 1) * this.blockSize - 1);

      if (left <= right) {
        this.lazy[i] += value;
      }
    }
  }

  getElement(index) {
    const blockIndex = Math.floor(index / this.blockSize);
    return this.arr[index] + this.lazy[blockIndex];
  }
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8];
const srd = new SquareRootDecomposition(arr);
srd.updateRange(1, 3, 10);
console.log(srd.getElement(2)); // Output: 12

5. Implementing Mo's Algorithm

Mo's Algorithm is a query processing technique used to efficiently handle range queries on arrays. It works by sorting queries based on a block size and processing them in batches to minimize the number of operations.

Feature	Description	Notes
Block Size	`sqrt(n)`	Determined by the array size to optimize query processing
Query Sorting	Sort by block index, then by right endpoint	Improves cache locality and reduces updates
Time Complexity	O((n + q) * sqrt(n))	Where n is array size and q is number of queries

Example: Implementing Mo's Algorithm

function moAlgorithm(arr, queries) {
  const blockSize = Math.ceil(Math.sqrt(arr.length));
  const sortedQueries = queries.map((q, i) => ({ ...q, index: i })).sort((a, b) => {
    const blockA = Math.floor(a.left / blockSize);
    const blockB = Math.floor(b.left / blockSize);
    if (blockA !== blockB) return blockA - blockB;
    return a.right - b.right;
  });

  const result = new Array(queries.length);
  let currentLeft = 0;
  let currentRight = -1;
  let currentSum = 0;

  for (const query of sortedQueries) {
    while (currentLeft < query.left) {
      currentSum -= arr[currentLeft];
      currentLeft++;
    }

    while (currentLeft > query.left) {
      currentLeft--;
      currentSum += arr[currentLeft];
    }

    while (currentRight < query.right) {
      currentRight++;
      currentSum += arr[currentRight];
    }

    while (currentRight > query.right) {
      currentSum -= arr[currentRight];
      currentRight--;
    }

    result[query.index] = currentSum;
  }

  return result;
}

// Example usage:
const arr = [1, 2, 3, 4, 5];
const queries = [
  { left: 0, right: 2 },
  { left: 1, right: 3 }
];
console.log(moAlgorithm(arr, queries)); // [6, 9]

Note: Mo's Algorithm is particularly useful for problems where queries are static and can be preprocessed. It trades off preprocessing time for faster query responses.

6. Solving Range Minimum Query

Operation	Description	Time Complexity	Space Complexity
Preprocessing	Build block minimums array	`O(n)`	`O(n)`
Query Range Min	Find minimum in range `[l, r]`	`O(√n)`	`O(1)`

Example: Range Minimum Query Implementation

class SquareRootDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.blocks = new Array(Math.ceil(this.n / this.blockSize)).fill(0);
    this.arr = arr;

    // Preprocessing: compute min for each block
    for (let i = 0; i < this.n; i++) {
      const blockId = Math.floor(i / this.blockSize);
      if (i % this.blockSize === 0) {
        this.blocks[blockId] = arr[i];
      } else {
        this.blocks[blockId] = Math.min(this.blocks[blockId], arr[i]);
      }
    }
  }

  rangeMinQuery(l, r) {
    let minVal = Infinity;

    let blockStart = Math.floor(l / this.blockSize) * this.blockSize;
    let blockEnd = blockStart + this.blockSize - 1;

    // Check if left and right are in same block
    if (l >= blockStart && r <= blockEnd) {
      for (let i = l; i <= r; i++) {
        minVal = Math.min(minVal, this.arr[i]);
      }
      return minVal;
    }

    // Left block
    while (l <= r && l % this.blockSize !== 0) {
      minVal = Math.min(minVal, this.arr[l]);
      l++;
    }

    // Right block
    while (l <= r && r % this.blockSize !== 0) {
      minVal = Math.min(minVal, this.arr[r]);
      r--;
    }

    // Middle blocks
    while (l <= r) {
      const blockId = Math.floor(l / this.blockSize);
      minVal = Math.min(minVal, this.blocks[blockId]);
      l += this.blockSize;
    }

    return minVal;
  }
}

// Example usage:
const arr = [1, 3, 2, 7, 9, 11];
const srd = new SquareRootDecomposition(arr);
console.log(srd.rangeMinQuery(1, 4)); // Output: 2

Note: The block size is chosen as ⌈√n⌉ to balance preprocessing and query time.

7. Implementing Point Update

Point updates in square root decomposition involve updating a single element in the array and reflecting that change in the corresponding block in the decomposed structure.

Operation	Description	Time Complexity	Space Complexity
update(index, value)	Updates the element at `index` to `value`	`O(1)`	`O(1)`

Example: Updating an Element

const sqrtDecomp = {
  blockSum: [0, 0, 0],
  blockSize: 2,
  array: [1, 2, 3, 4, 5, 6]
};

function update(index, value) {
  const blockIndex = Math.floor(index / sqrtDecomp.blockSize);
  const diff = value - sqrtDecomp.array[index];
  sqrtDecomp.array[index] = value;
  sqrtDecomp.blockSum[blockIndex] += diff;
}

update(2, 10);
console.log(sqrtDecomp.blockSum); // [3, 4, 6] - block 0 updated from 3 to 10

8. Optimizing Query Complexity

Operation	Time Complexity	Space Complexity	Notes
Query Range Sum	`O(√n)`	`O(1)`	With block size `√n`, optimal for range queries
Update Element	`O(1)`	`O(1)`	Direct update in block
Block Size Optimization	`O(√n)`	`O(n)`	Optimal block size for minimizing query cost

Example: Optimized Query Implementation

class SquareRootDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.blocks = new Array(this.blockSize).fill(0);
    this.buildBlocks(arr);
  }

  buildBlocks(arr) {
    for (let i = 0; i < this.n; i++) {
      const blockId = Math.floor(i / this.blockSize);
      this.blocks[blockId] += arr[i];
    }
  }

  queryRange(left, right) {
    let sum = 0;
    let startBlock = Math.floor(left / this.blockSize);
    let endBlock = Math.floor(right / this.blockSize);

    if (startBlock === endBlock) {
      for (let i = left; i <= right; i++) {
        sum += this.arr[i];
      }
    } else {
      let i = left;
      while (i < (startBlock + 1) * this.blockSize && i <= right) {
        sum += this.arr[i];
        i++;
      }

      for (let j = startBlock + 1; j < endBlock; j++) {
        sum += this.blocks[j];
      }

      i = endBlock * this.blockSize;
      while (i <= right) {
        sum += this.arr[i];
        i++;
      }
    }

    return sum;
  }
}

Note: Using √n block size ensures optimal query complexity of O(√n) for range sum queries.

9. Implementing Range Add Query

Range Add Query (RAQ) is a common operation in square root decomposition where we need to add a value to all elements in a given range. This operation is often used in dynamic range queries and updates.

Operation	Description	Time Complexity	Space Complexity
Update Range	Adds a value to all elements in the range [l, r]	O(√n)	O(n)
Query Range	Returns sum of elements in the range [l, r]	O(√n)	O(1)

Example: Range Add Query Implementation

class SquareRootDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.blockSize = Math.ceil(Math.sqrt(this.n));
    this.blocks = new Array(this.blockSize).fill(0);
    this.lazy = new Array(this.blockSize).fill(0);
    this.arr = [...arr];
    
    // Initialize blocks with actual values
    for (let i = 0; i < this.n; i++) {
      const blockId = Math.floor(i / this.blockSize);
      this.blocks[blockId] += this.arr[i];
    }
  }

  updateRange(l, r, value) {
    let blockStart = Math.floor(l / this.blockSize);
    let blockEnd = Math.floor(r / this.blockSize);

    if (blockStart === blockEnd) {
      // Same block
      for (let i = l; i <= r; i++) {
        this.arr[i] += value;
        this.blocks[blockStart] += value;
      }
    } else {
      // Different blocks
      let i = l;
      while (i < this.n && i % this.blockSize !== 0) {
        this.arr[i] += value;
        this.blocks[Math.floor(i / this.blockSize)] += value;
        i++;
      }

      while (i <= r && i + this.blockSize <= r) {
        const blockId = Math.floor(i / this.blockSize);
        this.blocks[blockId] += value * this.blockSize;
        i += this.blockSize;
      }

      while (i <= r) {
        this.arr[i] += value;
        this.blocks[Math.floor(i / this.blockSize)] += value;
        i++;
      }
    }
  }

  queryRange(l, r) {
    let blockStart = Math.floor(l / this.blockSize);
    let blockEnd = Math.floor(r / this.blockSize);
    let sum = 0;

    if (blockStart === blockEnd) {
      // Same block
      for (let i = l; i <= r; i++) {
        sum += this.arr[i];
      }
    } else {
      // Different blocks
      let i = l;
      while (i < this.n && i % this.blockSize !== 0) {
        sum += this.arr[i];
        i++;
      }

      while (i <= r && i + this.blockSize <= r) {
        sum += this.blocks[Math.floor(i / this.blockSize)];
        i += this.blockSize;
      }

      while (i <= r) {
        sum += this.arr[i];
        i++;
      }
    }

    return sum;
  }
}

// Example usage:
const arr = [1, 2, 3, 4, 5, 6, 7, 8];
const srd = new SquareRootDecomposition(arr);
srd.updateRange(1, 3, 5); // Add 5 to elements from index 1 to 3
console.log(srd.queryRange(0, 2)); // Sum of elements from index 0 to 2

Note: The lazy propagation technique can be used to optimize range updates further by deferring the actual updates until they are needed.

10. Solving Distinct Elements Query

Operation	Description	Time Complexity	Space Complexity
Query Range	Given a range [L, R], find number of distinct elements in that range	O(√N)	O(1)

Example: Counting Distinct Elements in Range

function countDistinctInRange(arr, L, R) {
  const block = Math.ceil(Math.sqrt(arr.length));
  const freq = new Map();
  let distinct = 0;

  for (let i = L; i <= R; i++) {
    if (!freq.has(arr[i])) {
      freq.set(arr[i], 1);
      distinct++;
    } else {
      freq.set(arr[i], freq.get(arr[i]) + 1);
    }
  }

  return distinct;
}

Note: For large arrays, precompute block-wise frequency maps to optimize queries.

11. Handling Dynamic Updates

Operation	Description	Time Complexity	Notes
Update element at index i	Modify value at a specific index in the array	`O(1)`	Requires updating both the original array and the block values
Recompute block sums	Recalculate sum for affected blocks after update	`O(√n)`	Block size is `√n`, so at most `√n` blocks need recalculation
Range query after update	Query sum over a range after updates	`O(√n)`	Same as initial query, but with updated block values

Example: Updating and Querying

const arr = [1, 2, 3, 4, 5, 6, 7, 8];
const blockSize = Math.ceil(Math.sqrt(arr.length));
let blocks = new Array(blockSize).fill(0);

// Initialize blocks
for (let i = 0; i < arr.length; i++) {
    const blockIndex = Math.floor(i / blockSize);
    blocks[blockIndex] += arr[i];
}

// Update element at index 2 to 10
const oldVal = arr[2];
arr[2] = 10;
const blockIndex = Math.floor(2 / blockSize);
blocks[blockIndex] += (10 - oldVal);

// Query sum from index 1 to 5
let sum = 0;
for (let i = 1; i <= 5; i++) {
    const blockStart = Math.floor(i / blockSize) * blockSize;
    const blockEnd = Math.min(blockStart + blockSize - 1, arr.length - 1);
    if (i >= blockStart && i <= blockEnd) {
        sum += arr[i];
    }
}
console.log(sum); // 19 (2+10+4+3)

Note: Dynamic updates require maintaining block sums and updating them when elements change. The cost of an update is O(1) for the array and O(√n) for block recomputation.