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 · 3 of 3

Difference arrays

Apply many range additions with two writes each, then recover every value with one running sum.

1,131 words · 6 min read

Lesson Problems10 Reading4
  • usaco.guide More on Prefix Sums Its difference arrays section solves Greg and Array on Codeforces, where the updates themselves arrive in ranges. usaco.guide (opens in a new tab)
  • oi-wiki.org 前缀和 & 差分 (Prefix sums and differences) Difference arrays in one dimension, in two or more dimensions, and along the paths of a tree. oi-wiki.org (opens in a new tab)

More links2

  • Difference Array Techniquelabuladong.online (opens in a new tab)
  • CF Blog – Difference Array Techniquecodeforces.com (opens in a new tab)
Lesson: Difference arrays
Overview Roadmap Problem sets Log in