Range Update Range Query

BIT Revisited

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

Implementation

Problems

Lazy Segment Tree

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.

Copy
#include <iostream>
using ll = long long;
using namespace std;

const int maxN = 2e5 + 5;

int N, Q;
int a[maxN];

struct node {

Tutorial

Problems