PrevNext
Rare
 0/14

Range Update Range Query

Authors: Benjamin Qi, Mihnea Brebenel

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

C++

#include <bits/stdc++.h>
using namespace std;
Code Snippet: BIT Code (from PURS module) (Click to expand)
int main() {
int test_num;
cin >> test_num;
for (int t = 0; t < test_num; t++) {
int n, q;

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 push_down function, all you need is a regular range-sum segment tree to solve the question.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/**
* Represents the type of lazy update being done.
* NONE = if there's no lazy update to be performed.
*/
enum QueryType { ADD, SET, NONE };

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
PlatinumEasy
Show TagsLazy SegTree
CSESEasy
Show TagsLazy SegTree
Old GoldEasy
Show TagsLazy SegTree
IOINormal
Show TagsLazy SegTree
IOINormal
Show TagsCoordinate Compression, Lazy SegTree
PlatinumNormal
Show TagsEuler Tour, Lazy SegTree, PURS
JOIVery Hard
Show TagsLazy SegTree
DMOPCVery 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