Zadanie - chodowla chonkersów

Question

Witam!

Mam takie zadanie:

Zadanie

Zajmujesz się hodowlą chonkersów (chonker - a fat but photogenic cat). W swojej hodowli masz dokładnie N chonkersów, i-ty z nich ma wagę wi. Każdego dnia musisz karmić swoje koty, aby pozostały tak zacnymi chonkersami, jak są do tej pory. Każdego dnia pora karmienia następuje Q razy. Każde karmienie odbywa się następująco - zaczynasz sypać karmę począwszy od pewnego l-tego kotka i przesuwasz się w prawo dopóki nie dojdziesz do r-tego kotka. Każdy kotek potrzebuje tyle karmy, ile sam waży. Z pewnością zatem zauważył*ś, że potrzebujesz wl + wl + 1 + wl + 2 + ... + wr - 1 + wr karmy, aby nakarmić kotki. Twoim zadaniem jest napisać program, który dla danego planu karmienia powie, ile za każdym karmieniem powinieneś mieć przygotowanej karmy!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, nie większa niż 105. W następnym wierszu znajduje się ciąg liczb w1, w2, wN, oznaczający wagi kolejnych chonkersów, każdy chonkers waży co najwyżej 104. W następnym wierwszu wejścia znajduje się jedna liczba naturalna Q nie większa niż 105, oznaczająca liczbę karmień w ciągu dnia. W następnych Q wierszach znajdują się opisy kolejnych karmień. Każdy opis składa się z dwóch liczb naturalnych l oraz r oznaczających, że dane karmienie zaczynamy od l-tego kotka i kończymy na r-tym.

Wyjście

Dla każdego opisu karmienia należy wypisać jedną liczbę naturalną, oznaczającą ilość karmy potrzebną podczas tego karmienia.

Przykład

Dla danych wejściowych

5

5 1 4 3 1

4

1 2

5 5

3 4

1 3

poprawną odpowiedzią jest

6 1 7 10

generalnie kod mam zrobiony i wygląda tak:

#include <iostream>
using namespace std;
int tab[100001];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, q, i , r, lk = 0;
    cin >> n;

    for (int i = 1;i <= n;i++)
    {
        cin >> tab[i];
    }
    cin >> q;
    for (int ii = 1;ii <= q;ii++)
    {
        cin >> i >> r;
        for (int b = i;b <= r;b++)
        {
            lk = lk + tab[b];
        }
        cout << lk << "\n";
        lk = 0;
    }

     return 0;
}

ale chciałbym, żeby ktoś podpowiedział mi jak to zrobić bez fora w forze, by program nie był za bardzo złożony

Z góry dziękuję

Answer 1

Możesz skorzystać z sum prefiksowych i wtedy będziesz miał rozwiązanie w O(n + q)