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]$.

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

• Find the sum of all values in range $[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, $\texttt{lzAdd}$ will represent the lazy tag for the range add query and $\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 $\texttt{lzSet}$ equals 0: Simply add the new value to the pre-existing value.

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

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

• Range set when $\texttt{lzAdd}$ doesn't equal 0: Again, simply update the $\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

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
IOINormal
PlatinumNormal
Show TagsEuler Tour, Lazy SegTree, PURS
JOIVery Hard
Show TagsLazy SegTree
DMOPCVery Hard
Show TagsLazy SegTree

### 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!