Запрос максимальной суммы диапазона с использованием разреженной таблицы - PullRequest
Новая
       21

Запрос максимальной суммы диапазона с использованием разреженной таблицы

0 голосов
/ 20 января 2019

I Реализован запрос максимальной суммы диапазона с использованием разреженной таблицы. Я знаю, что более эффективным подходом будет использование деревьев сегментов.

Что я пробовал:

Я рассчитываю максимальную сумму в диапазоне(i,2^j-1) для всех возможных значений i и j и сохранения их в таблице

, где i - индекс, а j обозначает степень 2 (2 ^ j обозначает длину сегмента от i, для которого мывычисление максимальной суммы)

Теперь, используя приведенную выше таблицу, мы можем ответить на запросы

Ввод:

3

-1 2 3

1

1 2

ожидаемый результат:

2

фактический выход:

«неправильный ответ (значение мусора)»

нам нужно указать максимальную непрерывную сумму в данном запросе Ссылка на вопрос spoj gss1

Пожалуйста, помогите: 

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
const int k = 16;
const int N = 1e5;
const int ZERO = 0; // ZERO + x = x + ZERO = x (for any x)

long long table[N][k + 1]; // k + 1 because we need to access table[r][k]
long long  Arr[N];

int main()
{
    int n, L, R, q;
    cin >> n; // array size
    for(int i = 0; i < n; i++)
        cin >> Arr[i];

    // build Sparse Table
    for(int i = 0; i < n; i++)
        table[i][0] = Arr[i];

    for(int j = 1; j <= k; j++) {
        for(int i = 0; i <= n - (1 << j); i++)
            //table[i][j] = table[i][j - 1] + table[i + (1 << (j - 1))][j - 1];
            table[i][j] = max(table[i][j-1],max(table[i+(1<<(j-1))][j-1],table[i+(1<<(j-1))][j-1]+table[i][j-1]));
    }

    cin >> q; // number of queries
    for(int i = 0; i < q; i++) {
        cin >> L >> R; // boundaries of next query, 0-indexed
        long long int answer = LLONG_MIN;
        for(int j = k; j >= 0; j--) {
            if(L + (1 << j) - 1 <= R) {
                answer = max(answer,answer + table[L][j]);
                L += 1 << j; // instead of having L', we increment L directly
            }
        }
        cout << answer << endl;
    }
    return 0;
}

ссылка на вопрос Spoj Gss1

...