W pierwszej kolejności proponowałbym wyłączyć synchronizację std z iostream (ios::sync_with_std(0)). Przy takim dużym wejść i wyjściu używanie cout << endl zabija performance.

Poza tym koncepcje wydaje się prawidłowa. Jeśli nie ma błędów w indeksach i zakresach, to powinno działać.

W kwestii buforowanie wejścia i wyjścia, to sugerowałbym jeszcze wyłączyć powiązanie pomiędzy std::cin i std::cout przy pomocy std::cin.tie(nullptr) (bez tego operacje na cin powodują czyszczenie bufora cout).

W powyższym rozwiązaniu jest kilka zbędnych elementów które aż czterokrotnie zwiększają zużycie pamięci. Tylko jedna z zadeklarowanych tablic jest używana w rozwiązaniu. Dodatkowo tablica ta przechowuje strukturę w której używane jest tylko jedno z trzech pól.

Jeśli chodzi o same struktury danych, to drzewo Fenwicka byłoby tu nieco szybsze niż drzewo przedziałowe.