Rare
0/13
Range Update Range Query
Author: Benjamin Qi
Prerequisites
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.
| Resources | |||
|---|---|---|---|
| GFG | |||
| GFG | |||
| bmerry | |||
Implementation
| Resources | |||
|---|---|---|---|
| Benq | |||
This section is not complete.
Feel free to file a request to complete this using the "Contact Us" button.
Problems
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| CSES | Easy | Show TagsBIT-Range | Show Sketch | |||
| Baltic OI | Normal | Show TagsBIT-Range, Binary search | View Solution | |||
| IOI | Normal | Show TagsBIT-Range, Binary search | External Sol |
Lazy Segment Tree
Focus Problem – read through this problem before continuing!
Tutorial
| Resources | |||
|---|---|---|---|
| CF | |||
| CPH | short description | ||
| CSA | interactive | ||
| cp-algo | adding on segments, assigning | ||
| CF | code is more confusing than recursive version | ||
Implementation
This section is not complete.
Feel free to file a request to complete this using the "Contact Us" button.
Problems
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| YS | Easy | Show TagsLazy SegTree | View Solution | |||
| Plat | Easy | Show TagsLazy SegTree | External Sol | |||
| Old Gold | Easy | Show TagsLazy SegTree | External Sol | |||
| IOI | Normal | External Sol | ||||
| IOI | Normal | External Sol | ||||
| Plat | Normal | Show TagsLazy SegTree | External Sol | |||
| JOI | Very Hard | Show TagsLazy SegTree | External Sol | |||
| DMOJ | Very Hard | Show TagsLazy SegTree | Check DMOJ |
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!