BIT Revisited

Binary Indexed Trees can support range increments and range sum queries.

Resources

Explanation

First, we can reduce the problem of performing range add and range sum queries into an easier problem: adding on a suffix, and querying the sum of a prefix of our array.

Let our array be $a$, and the prefix sum array of $a$ be $b$. If we add $x$ to the range $[p, n]$, then, for every $i \geq p$, we add $x \cdot (i - p + 1)$ to each $b_i$ in the range. To query the prefix of $[1, p]$, we can consider the following process:

1. Find the sum of all the range additions affecting the index $p$. Let this number be $x$. For now, we evaluate their contribution to be equal to $p \cdot x$. We can keep track of all the range additions that affect each indice using a BIT.
2. Step 1 obviously overcounts. To fix this overcounting, note that for each suffix addition query, the true contribution to the array only differs by a constant amount compared to the value obtained by step 1. This value is $x \cdot (p - 1)$, if we update the suffix of $[p, n]$ by adding $x$. Thus, we use a separate BIT that keeps track of all of the corrections to the contribution evaluated by step 1.

We can perform range addition and range summation queries by performing multiple suffix addition and prefix sum queries.

Implementation

Time Complexity: $\mathcal{O}(N + Q\log{N})$

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

Lazy segment trees allow us to efficiently perform range updates and range queries.

Lazy segment trees allow us to perform range updates and range queries in $\mathcal{O}(\log{N})$ time. In order to perform range updates in $\mathcal{O}(\log{N})$, we lazily apply updates to the nodes. That is, we store updates on the nodes that compose the range we are updating, and lazily apply the updates when we walk down the tree.

As an example, let's consider writing a lazy segment tree that supports range addition and range summation. We would have our tree nodes contain the sum on the range, and keep a separate array keeping track of the lazy additions we have to do for each node. If we were to add $3$ to our array $a[0 \ldots n - 1]$, then we would need to set a lazy update at the root of our tree indicating that we need to add $3$ to the entire range. Then, if we were to query a subarray of $a$, we need to "push down" the updates at the root down to its children.

It is crucial that we always push down all the previous updates when traversing down the tree. If we don't, the following things can happen:

1. If we have two updates that affect two nodes, where one node is an ancestor of another, then one of the updates will be ignored.
2. The updates will be applied in incorrect order, which matters if the updates are not commutative.

For a concrete example for why point 1 can be an issue, consider the following sequence of updates.

1. $+3$ to all values on $[1, 4]$
2. $+5$ to all values on $[1, 2]$
3. Query sum on $[1, 8]$

If we don't push down the updates when traversing down the tree, then the first update will get ignored in our sum query.

Horrible Queries Implementation

Time Complexity: $\mathcal{O}(N + Q \log{N})$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<T> tree;
	vector<T> lazy;

Explanation

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.

Implementation

Time Complexity: $\mathcal{O}(N + Q\log{N})$

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 };

Lazy segment trees are notorious for being difficult to make generic. The AtCoder template is an example of a fully generic template.

Below is an implementation of the focus problem using a somewhat generic template. The idea is that we supply an Info and Tag class into the template. The Tag class handles lazy updates, and how lazy updates interact with each other. Meanwhile, the Info class handles the tree values, and how lazy updates are applied to given tree values.

Some key implementation details:

1. We must give lazy tags and tree values neutral values. That is, we need to set the values inside the classes to some value that won't affect our answers.
2. For the apply function in the Info and Tag functions, we need to ensure that we aren't applying neutral updates to any nodes.

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class Info, class Tag> class LazySegtree {
  private:
	const int n;
	vector<Info> tree;
	vector<Tag> lazy;

Problems