Table of Contents

BIT Revisited Implementation Problems Lazy Segment Tree Solution - Range Updates & Sums Tutorial Problems Edit this page

Rare

0/14

Range Update Range Query

Author: Benjamin Qi

Prerequisites

Gold - Point Update Range Sum

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

Table of Contents

BIT Revisited Implementation Problems Lazy Segment Tree Solution - Range Updates & Sums Tutorial Problems

BIT Revisited

Horrible Queries

Focus Problem – read through this problem before continuing!

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

Resources
GFG	Range Update Point Query
GFG	Range Update Range Query
bmerry	Interval Trees

Implementation

Resources
Benq	BITrange

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	Polynomial Queries	Easy	Show Tags 1DRQ
	Baltic OI	2011 - Growing Trees	Normal	Show Tags 1DRQ, Binary search
	IOI	2007 - Sails	Normal	Show Tags 1DRQ, Binary search

Lazy Segment Tree

Range Updates & Sums

Focus Problem – read through this problem before continuing!

Solution - Range Updates & Sums

Solution

Tutorial

Resources
CF	EDU: Segment Tree Pt 2
CPH	28.1 - Segment Trees Revisited	short description
CSA	Segment Trees	interactive
cp-algo	Segment Tree	adding on segments, assigning
CF	Efficient and easy segment trees	code is more confusing than recursive version

Problems

Status	Source	Problem Name	Difficulty	Tags
	YS	Range Affine Range Sum	Easy	Show Tags Lazy SegTree
	Plat	Counting Haybales	Easy	Show Tags Lazy SegTree
	Old Gold	The Lazy Cow	Easy	Show Tags Lazy SegTree
	CSES	Prefix Sum Queries	Normal
	IOI	2014 - Wall	Normal
	IOI	2005 - Mountain	Normal
	Plat	Snow-Cow	Normal	Show Tags Lazy SegTree
	JOI	2018 - Bubble Sort 2	Very Hard	Show Tags Lazy SegTree
	DMOJ	Victor Identifies Software	Very Hard	Show Tags Lazy 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!