From 7761f38957fecd5f45bc62d55e9a77636a2b11d5 Mon Sep 17 00:00:00 2001
From: Dushyant Singh
Date: Sun, 12 Dec 2021 17:22:34 +0530
Subject: fix off by one in sparse table

Given code fails for `query(0, n - 1)`
Problem to test on https://codeforces.com/contest/1549/problem/D---
 Data Structures/sparse_table.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Data Structures/sparse_table.cpp b/Data Structures/sparse_table.cpp
index c303930..841674e 100644
--- a/Data Structures/sparse_table.cpp	
+++ b/Data Structures/sparse_table.cpp	
@@ -8,7 +8,7 @@ public:
 		for (int i = 0; i <= log(N); i++) st[i].resize(N);
 		for (int i = 0; i < N; i++) st[0][i] = A[i];
 		for (int i = 1; i <= log(N); i++) {
-			for (int j = 0; j + (1 << i) < N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
+			for (int j = 0; j + (1 << i) <= N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
 		}
 	}
 
-- 
cgit v1.2.3-70-g09d2