Drzewo przedziałowe typu (punkt, przedział)

Drzewo przedziałowe typu (przedział, punkt)

Zadanie: Policz sumę w przedziale

Napisz program, który policzy sumę liczb z przedziału obustronnie domkniętego.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość liczb w przedziale (n <100001). W drugim wierszu n liczb naturalnych, każda z przedziału [0..32000]. Następnie liczba q określająca liczbę zapytań. Każde zapytanie składa się z trzech liczb option, a oraz b, gdzie option przyjmuje dwie wartości: {0, 1}, natomiast a i b to liczby naturalne należące do przedziału [0..32000]. Jeśli option ma wartość 0 to wyznaczamy sumę liczb z przedziału [a..b], w przeciwnym razie aktualizujemy liczbę stojącą na pozycji a na wartość b.

Wyjście

Dla każdego option równego 0 wypisujemy sumę liczb z przedziału [a..b].
Uwaga! Pozycje liczb numerujemy od 0.

//Drzewo przedziałowe typu (punkt, przedział)
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;
int M;
int *tab;
//aktualizacja wartości stojącej na pozycji k na wartość val w czasie O(log)
void insert(int k, int val)
{
	k+=M;
	val -= tab[k]; //ustalenie o ile zmieni się aktualizowana wartość
	while(k>0) //dopóki nie dojdziemy do korzenia
	{
		tab[k] += val;
		k>>=1;
	}
}
//wyznaczenie sumy liczb z przedziału [a..b] w czasie O(log)
int query(int a, int b)
{
	int w = 0; //wynik;
	a+=M;b+=M; //właściwe ustawienie przedziału
	w = tab[a]; //dodanie do wyniku wartości na liściu będącym początkiem przedziału
	if(a!=b)	//jeśli przedział nie jest jednoelementowy
		w += tab[b]; //dodanie do wyniku wartości na liściu będącym końcem przedziału
	while((a>>1) != (b>>1)) //jeśli wierzchołki nie mają wspólnego ojca
	{
		if(a%2 == 0) //lewy syn na lewej ścieżce
			w += tab[a+1]; //zwiększamy wynik o wartość wszystkich liści poddrzewa o korzeniu w tab[a+1]
		if(b%2 == 1) //prawy syn na prawej ścieżce
			w += tab[b-1]; //zwiększamy wynik o wartość wszystkich liści poddrzewa o korzeniu w tab[b-1]
		a>>=1; //przejście w górę drzewa
		b>>=1; //przejście w górę drzewa
	}
	return w;
}

int main()
{
	//przyspieszanie operacji na we/wy
	ios_base::sync_with_stdio(0);
	cin.tie();cout.tie();
	//--------------------------------
			
	int q, option, a, b, val, k, n;
	cin>>n;
	
	M = 1; 
	while(M<=100000) M<<=1; //wyznaczenie namniejszej potęgi liczby 2 mieszczącej wszystkie liczby z przedziału
	
	tab = new int [M<<1];
	
	for(int i=0;i<(M<<1);i++) tab[i]=0; 
	
	for(int i=0;i<n;i++){
		cin>>a;
		insert(i, a);
	}
	cin>>q;
	
	while(q--)
	{
		cin>>option;

		if(option == 0)
		{
			cin>>a>>b;
			cout<<query(a, b)<<endl;
		}
		else
		{
			cin>>a>>b;
			insert(a, b);
		}
	}
	return 0;
}

Przykład:

Wejście:

5
2 3 2 1 3
5
0 0 4
0 1 3
1 2 6
1 4 4
0 0 4

Wyjście:

11
6
16