# Range Update Range Query

Authors: Benjamin Qi, Mihnea Brebenel

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

### Prerequisites

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

Resources | ||||
---|---|---|---|---|

GFG | ||||

GFG | ||||

bmerry |

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

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 – 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 `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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

YS | Easy | ## Show TagsLazy SegTree | |||

Platinum | Easy | ## Show TagsLazy SegTree | |||

CSES | Easy | ## Show TagsLazy SegTree | |||

Old Gold | Easy | ## Show TagsLazy SegTree | |||

IOI | Normal | ## Show TagsLazy SegTree | |||

IOI | Normal | ## Show TagsCoordinate Compression, Lazy SegTree | |||

Platinum | Normal | ## Show TagsEuler Tour, Lazy SegTree, PURS | |||

JOI | Very Hard | ## Show TagsLazy SegTree | |||

DMOPC | Very 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!