Sparse Table
(content/data_structures/sparse_table.h)

• View this file on GitHub
• Last update: 2024-02-01 17:09:56-05:00

There is a separate template for binary lifting. This one is just for range queries.

Depends on

• My starter code (content/utils/template.h)

Verified with

• tests/sparse_table.test.cpp

Code

#pragma once
#include "../utils/template.h"

/**
 * @brief Sparse Table
 * @docs docs/sparse_table.md
 */

template<class T> struct sparse_table{
	
	int n; vector<vector<T>> sp;
	function<T(T, T)> merge;
	
	T query(int l, int r){
		int k = __lg(r-l+1);
		return merge(sp[k][l], sp[k][r-(1<<k)+1]);
	}
	void build(vector<T> v, function<T(T, T)> f){
		merge = f;
		n = (int)size(v);
		sp.resize(__lg(n)+1);
		sp[0] = v;
		for(int i = 1; i <= __lg(n); i++){
			sp[i].resize(n);
			for(int j = 0; j+(1<<i)-1 < n; j++){
				sp[i][j] = merge(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
			}
		}
	}
};

#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/data_structures/sparse_table.h"

/**
 * @brief Sparse Table
 * @docs docs/sparse_table.md
 */

template<class T> struct sparse_table{
	
	int n; vector<vector<T>> sp;
	function<T(T, T)> merge;
	
	T query(int l, int r){
		int k = __lg(r-l+1);
		return merge(sp[k][l], sp[k][r-(1<<k)+1]);
	}
	void build(vector<T> v, function<T(T, T)> f){
		merge = f;
		n = (int)size(v);
		sp.resize(__lg(n)+1);
		sp[0] = v;
		for(int i = 1; i <= __lg(n); i++){
			sp[i].resize(n);
			for(int j = 0; j+(1<<i)-1 < n; j++){
				sp[i][j] = merge(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
			}
		}
	}
};

Back to top page