Lesson overview · Free interview practice

Sqrt Decomposition

Divide problems into blocks for efficient query processing.

Topics in the full lesson
  • Concept and Use Cases
  • Key Concepts
  • Time and Space Complexity
  • Sqrt Decomposition Implementation
  • Range Minimum Query with Updates
  • Practical Tips and Tricks
  • Common Gotchas
  • Advanced Topics
  • Interview Tips and Tricks
  • Common Mistakes

Practice Problems

Work through a question before revealing its explanation. These questions and answers are free; Premium adds the full lesson walkthrough, examples and implementation detail.

Completion marks record your own progress, not an automatically checked result. The task type does not determine whether it is optional.

CodingMedium

Range Addition

Question

You are given an integer length and an array updates where updates[i] = [startIdx, endIdx, inc]. You have an array arr of length length initialized to 0. For each update, add inc to every element from index startIdx to endIdx (inclusive). Return the final array.

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Practice on LeetCode
CodingHard

Count of Smaller Numbers After Self

Question

Given an integer array nums, return an array counts of the same length where counts[i] is the number of elements nums[j] with j > i that are smaller than nums[i].

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Practice on LeetCode

Explore the full Sqrt Decomposition material

Premium includes the complete lessons and implementation references. Free practice questions remain available without a subscription.

All course tracks & premium content
From basics to advanced masterclasses
Built for JS/TS developers like you
Real-world tips & common pitfalls
Upgrade to Premium