WhiteBox
DSA
Start coding DSA Beyond LeetCode System Design AI Engineering White Room
RoadmapProblem sets
Quizzes Dan Ladder Contests Templates Graph Editor
Guides Library
Login Sign up
Sign up Log in

Workspaces

Start coding DSA Beyond LeetCode System Design AI Engineering White Room

DSA

Overview Roadmap Problem sets Quizzes Dan Ladder Contests Templates Graph Editor CP Guessr

Library

Library Guides

Community

Leaderboard Contributors Refer & Earn Cosmetics

Tools

Resume Reviewer Job Boards Changelog

Arrays and searching 0/120

DSA 0 of 360 problems solved
0%
Overview

Curriculum

    1. Hashing 0/11
    2. Two pointers 0/12
    3. Sliding window 0/21
    4. Prefix sums 0/29
      1. Prefix sum technique 0/13
      2. 2D prefix sums 0/6
      3. Difference arrays 0/10
    5. Binary search 0/20
    6. Heaps 0/11
    7. Greedy and intervals 0/9
    8. Linked lists 0/8
    9. Data structure design
  1. DSA
  2. / Arrays and searching

Prefix sums · 1 of 3

Prefix sum technique

Store every prefix sum once, answer any range sum with one subtraction, and count subarrays by their sum with a map of prefix sums.

3,603 words · 17 min read

Lesson Problems13 Reading3

Books1

  • Competitive Programmer’s Handbook, Section 9.1: Static array queries Pages 84 and 85: the prefix sum array in under a page, and a sparse table for range minimum, the question prefix sums cannot answer. (opens in a new tab)

Links1

  • usaco.guide Introduction to Prefix Sums Range sums worked through on a six-value array, then a graded problem list that includes CSES Subarray Sums II and Subarray Divisibility, contest versions of this page's last two problems. usaco.guide (opens in a new tab)

More links1

  • Errichto - Prefix Sums: Problems, Code in C++ & Pythonyoutube.com (opens in a new tab)
Lesson: Prefix sum technique
Overview Roadmap Problem sets Log in