Range Update Range Query

BIT Revisited

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

Implementation

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

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

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

Problems