Optymalizacja kodu: Policzenie XOR na podanym przedziale

Question

Oto treść zadania:
Jankowi, dzięki intensywnym przygotowaniom, udało się dostać do finału OMJ. Oczywiście jako finalista Olimpiady umie już dodawać, więc w ramach przygotowań do finału wymyślił sobie nowe ćwiczenie: zapisuje na
kartce n liczb, a następnie wybiera dwie liczby całkowite a, b i oblicza XOR wszystkich zapisanych liczb od a-tej
do b-tej włącznie.
Niestety, finał OMJ został odwołany, więc Janek nie będzie miał możliwości sprawdzenia swoich umiejętności
na zawodach. Pomóż mu i napisz program obliczający poprawne odpowiedzi.
WEJŚCIE
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i q (1 ¬ n, q ¬ 106
) oznaczające odpowiednio
ile liczb zapisał Janek na kartce i ile pytań chce zadać.
W drugim wierszu znajduje się n liczb całkowitych z przedziału h0, 106
i – liczby zapisane przez Janka na kartce.
W każdym z następnych q wierszy znajdują się dwie liczby całkowite a i b (1 ¬ a ¬ b ¬ n), które oznaczają
odpowiednio numer pierwszej i ostatniej liczby przedziału, na którym należy policzyć XOR.
WYJŚCIE
Należy wypisać odpowiedzi na kolejne pytania Janka, każde w oddzielnej linii.
PRZYKŁAD
Wejście:
6 2
31 13 16 21 0 1
1 6
2 5
Wyjście:
22
8

Oto mój kod, który otrzymuje 40 punktów:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int t[n];
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    int sp[n];
    sp[0] = t[0];
    for(int i = 1; i < n; i++){
        sp[i] = sp[i - 1] ^ t[i];
    }
    int a, b;
    while(m--){
        cin >> a >> b;
        if(a == 1){
            cout << sp[b-1] << endl;
        }
        else {
            cout << (sp[b-1] ^ sp[a-2]) << endl;
        }
    }
}

Przekroczony został limit czasu. Czy ktoś pomógłby mi zoptymalizować kod?

Nie chodzi o to, że używam cout zamiast printf itp.

Comments

Spróbuj moze dodać to na początek maina:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

Answer 1

Na pierwszy rzut oka wygląda to na zadanie z drzewem przedziałowym. Mógłbyś dać link do zadania?

Comments

to jest klasyczne zadanie na xory na prefiksie, Drzewo przedziałowe to będzie overkill

---

Fakt, zdecydowanine łatwiejszy i szybszy będzie sposób z prefiksami. Ciekawe czy drzewo przedziałowe weszłoby na 100

---

Drzewo fenwicka powinno wejść na 100. No ale rozwiązanie które ma OP też powinno wejść na 100, a nie weszło, więc kto wie

---

@KumberTwZo, zadanko jest ze szkolnego sio2 i niestety nie mam jak dać linka. Jedyne co wiem, to to że w 3 z 5 testów limit czasu został przekroczony. Przyznam się szczerze, że nie wiem czym są drzewa przedziałowe. 

Answer 2

Trochę na szybkości zyskuje się zależnie od danych następującym kodem

#include <iostream>
using namespace std;
 
int main(
){  int n, m;
    cin >> n >> m;
    int t[n];
    for( int i = 0; i != n; i++ )
        cin >> t[i];
    int a[m], b[m];
    int max = 1;
    for( int i = 0; i != m; i++ )
    {   cin >> a[i] >> b[i];
        if( b[i] > max )
            max = b[i];
    }
    int sp[max];
    sp[0] = t[0];
    for( int i = 1; i != max; i++ )
        sp[i] = sp[ i - 1 ] ^ t[i];
    for( int i = 0; i != m; i++ )
    {   int r;
        if( a[i] == 1 )
            r = sp[ b[i] - 1 ];
        else
            r = sp[ b[i] - 1 ] ^ sp[ a[i] - 2 ];
        cout << r << endl;
    }
}

Do testów kompilowany bez optymalizacji.