Rare
0/14
Range Update Range Query
Author: Benjamin Qi
Lazy updates on segment trees and two binary indexed trees in conjunction.
Prerequisites
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.
Any help would be appreciated! Just submit a Pull Request on Github.
Problems
| Status | Source | Problem Name | Difficulty | Tags | |
|---|---|---|---|---|---|
| CSES | Easy | Show Tags1DRQ | |||
| Baltic OI | Normal | Show Tags1DRQ, Binary Search | |||
| IOI | Normal | 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
| Status | Source | Problem Name | Difficulty | Tags | |
|---|---|---|---|---|---|
| YS | Easy | Show TagsLazy SegTree | |||
| Plat | Easy | Show TagsLazy SegTree | |||
| CSES | Easy | Show TagsLazy SegTree | |||
| Old Gold | Easy | Show TagsLazy SegTree | |||
| IOI | Normal | ||||
| IOI | Normal | ||||
| Plat | Normal | Show TagsLazy SegTree | |||
| JOI | Very Hard | Show TagsLazy SegTree | |||
| DMOJ | Very Hard | Show TagsLazy SegTree |