Informatyka-Programowanie

Question

Witam mam pytanie. Czy ten kod da się jakoś przyśpieszyć?

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	int l_tulipanow,l_zapytan,tulipanki;
	scanf("%d",&l_tulipanow);
	scanf("%d",&l_zapytan);
	int tab[l_tulipanow];
	for(int tulipanki=0;tulipanki<l_tulipanow;tulipanki++){
		scanf("%d",& tab[tulipanki]);
		
	}
	for(int j=0;j<l_zapytan;j++)
	{
		int a, b , suma=0;
		scanf("%d",&a);
		scanf("%d",&b);
		for(int z=a;z<=b;z++)
		{
			if(tab[z-1] == 1)
			{
				suma++;
			}
		}
		printf("%d\n",suma);
	}
   


return 0;
}

Comments

A działa wolno?

Co on ma w ogóle robić?

(i co to za temat pytania? Bo nie rozumiem za bardzo.)

Answer 1

Tak, da się, algorytmu nie przyspieszysz, bo coś innego niż pętla for zbytnio się nie da wymyślić, to, co możesz ulepszyć to struktura danych.

W twoim programie jest to zwykła tablica i spoko, ale pomyśl sobie co by było jakbyś wsadził tam drzewo binarne. Drzewo bardzo proste: każdy wierzchołek ma indeks początku przedziału, kończ przedziału i sumę czerwonych tulipanów w tym przedziale (oczywiście w korzeniu masz przedział [0, 500000], w jego synach [0,250000], [250000, 500000] i tak malejący o pół).Wysokość takiego drzewa to 19, bo 2^18 < 500000 < 2^19. Żeby obliczyć sumę, musiałbyś najpierw dotrzeć do odpowiednich wierzchołków, dodać z nich wartości i już. Jakbyś miał sumować liczby z przedziału [125000, 350000] to u ciebie trzeba by dodać 225000 liczb, w drzewie wykonać 4 if-y (żeby znaleźć wierzchołki) i dodać wartości w nich zawarte - 5 operacji.

Oczywiście koszt tworzenia takiego drzewa jest niezerowy, ale dla dużej ilości operacji dodawania (szczególnie na dużych przedziałach) zwraca się z nawiązką. Jak przedziały będą wąskie lub operacji będzie mało pętla for będzie szybsza.

Answer 2

Zadanie brzmi tak:

Wejście:

W pierwszym wierszu wejścia podawane są dwie liczby całkowite s, z (2 ≤ s, z ≤ 500000), oznaczające odpowiednio liczbę tulipanów oraz liczbę zapytań. W kolejnym wierszu znajduje się sekwencja s cyfr składająca się z 1 i 0, gdzie 1 oznacza czerwonego tulipana, a 0 żółtego. Każda cyfra jest oddzielona od poprzedniej pojedynczą spacją. W kolejnych z wierszach znajdują się dwie liczby całkowite a i b (1≤ a, b ≤ s, a≤b) oznaczające zapytanie o ilość czerwonych tulipanów z przedziału od a do b włącznie.

Wyjście: W każdym i wierszu jedna liczba całkowita równa ilości czerwonych tulipanów z przedziału a i b.