PrevNext
Rare
 0/14

Range Update Range Query

Author: Benjamin Qi

Lazy updates on segment trees and two binary indexed trees in conjunction.

BIT Revisited

Focus Problem – read through this problem before continuing!

Binary Indexed Trees can support range increments in addition to range sum queries.

Implementation

Resources
Benq

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show Tags1DRQ
Baltic OINormal
Show Tags1DRQ, Binary search
IOINormal
Show Tags1DRQ, Binary search

Lazy Segment Tree

Focus Problem – read through this problem before continuing!

Solution - Range Updates & Sums

Solution

Tutorial

Resources
CF
CPH

short description

CSA

interactive

cp-algo

adding on segments, assigning

CF

code is more confusing than recursive version

Problems

StatusSourceProblem NameDifficultyTags
YSEasy
Show TagsLazy SegTree
PlatEasy
Show TagsLazy SegTree
Old GoldEasy
Show TagsLazy SegTree
CSESNormal
IOINormal
IOINormal
PlatNormal
Show TagsLazy SegTree
JOIVery Hard
Show TagsLazy SegTree
DMOJVery Hard
Show TagsLazy SegTree

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext