Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template< class Data, Data (*oper)(Data, Data) >
- class SparseTable {
- Data **table; // [power][begin]
- int *powers;
- public:
- SparseTable(Data *array, int len) {
- powers = new int [len + 1];
- int pow = 0;
- for (int i = 1; i <= len; i++) {
- if ((1 << (pow + 1)) <= i)
- pow++;
- powers[i] = pow;
- }
- table = new Data *[++pow];
- table[0] = array;
- for (int cur_pow = 1; cur_pow < pow; cur_pow++) {
- int max_begin = len - (1 << cur_pow) + 1;
- table[cur_pow] = new Data [max_begin];
- for (int i = 0; i < max_begin; i++)
- table[cur_pow][i] = oper(table[cur_pow - 1][i],
- table[cur_pow - 1][i + (1 << (cur_pow - 1))]);
- }
- }
- Data get(int l, int r) {
- int pow = powers[r - l + 1];
- return oper(table[pow][l], table[pow][r - (1 << pow) + 1]);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement