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 – try your best to solve 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 – try your best to solve this problem before continuing!

Solution - Range Updates & Sums

This question asks you to support the following types of queries:

  • Add a value to all elements within the range [a,b][a,b].

  • Set all values within the range [a,b][a,b] to a certain value.

  • Find the sum of all values in range [a,b][a,b].

Consider the first two types of queries. A lazy tag will be created in each node of the tree for each type. In this solution, lzAdd\texttt{lzAdd} will represent the lazy tag for the range add query and lzSet\texttt{lzSet} will represent the lazy tag for the range set query.

Given the two different types of update queries, a total of four different situations might take place after any update:

  • Range add when lzSet\texttt{lzSet} equals 0: Simply add the new value to the pre-existing value.

  • Range add when lzSet\texttt{lzSet} doesn't equal 0: Add the new value to lzSet\texttt{lzSet} and clear lzAdd\texttt{lzAdd}.

  • Range set when lzAdd\texttt{lzAdd} equals 0: Simply update the lzSet\texttt{lzSet} value.

  • Range set when lzAdd\texttt{lzAdd} doesn't equal 0: Again, simply update the lzSet\texttt{lzSet} value since a set update will override all previous add updates.

Given the mechanics behind the pushdown function, all you need is a regular range-sum segment tree to solve the question.

#include <iostream>
using ll = long long;
using namespace std;
const int maxN = 2e5 + 5;
int N, Q;
int a[maxN];
struct node {

Tutorial

Resources
CF EDU
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
CSESEasy
Show TagsLazy SegTree
Old GoldEasy
Show TagsLazy SegTree
IOINormal
IOINormal
PlatNormal
Show TagsEuler Tour, Lazy SegTree, PURS
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