Drzewo potęgowe

Drzewo potęgowe

Na strukturze drzewa potęgowego wykonywać będziemy następujące operacje:

• aktualizacja wartości pewnej komórki tablicy w czasie O(log n),
• odczytywanie sumy wszystkich liczb z przedziału [a..b] w czasie O(log n).

Zadanie

Napisz program, który będzie wykonywał jedną z dwóch czynności:

• aktualizował zawortość komórki o indeksie i,
• wypisywał sumę liczb z przedziału [a..b].

Wejście

W pierwszym wierszu jedna liczba q określająca liczbę operacji (nie większa niż 10⁷).

W kolejnych q wierszach czynność, która może być następującej postaci:

• 0 [a] [b] — wypisanie sumy liczb z przedziału [a..b], (0 <= a <= b <= 10⁷)
• 1 [val] [index] — aktualizacja komórki o indeksie indeks na wartość val (0 <= index <= 10⁷, 0 <= val <= 10⁹

Wyjście

Dla każdego zapytania 0 wypisanie sumy liczb z przedziału [a..b].

//Drzewo potęgowe
//Wyznaczanie sumy w przedziale
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

int *tab; //tablica przechowująca drzewo potęgowe
int N;  //wielkość zbioru

void update(int val, int index) //aktualizacja wartości val pod indeksem index
{
	while(index <= N)
	{
		tab[index] += val;
		index += (index&(-index));
	}
}

long long query(int index) //wyznaczenie sumy z przedziału [1..index]
{
	long long s = 0;
	while(index > 0)
	{
		s+= tab[index];
		index -= (index&(-index));
	}
	return s;
}

int main()
{
	int q, a, b, t;
	
	cin>>N;
	tab = new int [N+1];
	
	for(int i=0;i<=N;i++)
		tab[i] = 0;  //wyzerowanie elementów drzewa
		
	for(int i=1;i<=N;i++)
	{
		cin>>a;
		update(a, i);
	}
			
	cin>>q;
	
	while(q--)
	{
		cin>>t>>a>>b;
		if(t) //t==1
		//zaktualizuj wartość stojącą pod indeksem a na wartość b
			update(b, a); 
		else
		//wyznacz sumę z przedziału [a..b]
			cout<<query(b) - query(a-1)<<endl;
	}
	
	return 0;
}