aboutsummaryrefslogtreecommitdiff
path: root/Data Structures
diff options
context:
space:
mode:
authorTa180m2019-08-02 21:47:29 -0500
committerGitHub2019-08-02 21:47:29 -0500
commit5eade53a767f76e6ab6f9667255576ab0f18046b (patch)
treecfa01c27c8f5c17ad29076b94cbe16495f1cb4a1 /Data Structures
parentab2fe10480ccb0c381cb47995c77e175c9413ad2 (diff)
Update sparse_table.cpp
Diffstat (limited to 'Data Structures')
-rw-r--r--Data Structures/sparse_table.cpp12
1 files changed, 7 insertions, 5 deletions
diff --git a/Data Structures/sparse_table.cpp b/Data Structures/sparse_table.cpp
index 423181b..88fbf86 100644
--- a/Data Structures/sparse_table.cpp
+++ b/Data Structures/sparse_table.cpp
@@ -1,16 +1,18 @@
-class sparse_table {
-private: int st[20][100000];
+template< typename T > class sparse_table {
+private: vector<T> st[20];
public:
int log(int x) { return 32 - __builtin_clz(x) - 1; }
- sparse_table(int N, int A[]) {
+ sparse_table(vector<T> &A) {
+ int N = A.size();
+ for (int i = 0; i <= log(N); i++) st[i].resize(N);
for (int i = 0; i < N; i++) st[i][0] = A[i];
for (int i = 0; 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 = 1; j + (1 << i) < N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
- int query(int i, int j) {
+ T query(int i, int j) {
int k = log(j - i + 1);
return min(st[k][i], st[k][j - (1 << k) + 1]);
}