Drzewo przedziałowe typu (przedział, punkt)

Drzewo przedziałowe typu (przedział, punkt)

Zadanie.

Ustawmy w rzędzie pewną liczbę pojemników i ponumerujmy je od 1 do n. Wykonujemy następujące operacje:

• dla opcji 1 zwiększamy każdy pojemnik od pozycji a do pozycji b o wartość val,
• dla opcji 0 wypisujemy wartość pojemnika na pozycji k.

Wejście

W pierwszym wierszu dwie liczby: liczba n określająca liczbę pojemników (nie więcej niż milion) oraz liczba q określająca liczbę zapytań (nie więcej niż milion).
Każde zapytanie składa się z jednej liczby określającej opcję oraz:

• jeśli opcja ma wartość 1, to podana będzie jeszcze jedna liczba k (0 < k <= n),
• jeśli opcja ma wartość 0, to podane są jeszcze trzy liczby a, b oraz val takie, że 0 < a <= b < 1000001, 0 < val < 1001.

Wyjście

Dla każdego zapytania z opcją 1 wypisz wartość pojemnika o numerze k.

//Drzewo przedziałowe typu (przedział, wartość)
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;
int M;
int *tab;
//zwiększenie wszystkich elementów przedziału [a..b] o val w czasie O(log)
void insert(int a, int b, int val)
{
	a+=M;b+=M; //właściwe ustawienie przedziału
	tab[a]+=val; //zwiększenie wartości na liściu
	if(a!=b)	//jeśli przedział nie jest jednoelementowy
		tab[b]+=val; 
	while((a>>1) != (b>>1)) //jeśli wierzchołki nie mają wspólnego ojca
	{
		if(a%2 == 0) //lewy syn na lewej ścieżce
			tab[a+1]+=val; //zwiększamy wartość o val dla wszystkich liści poddrzewa o korzeniu w tab[a+1]
		if(b%2 == 1) //prawy syn na prawej ścieżce
			tab[b-1]+=val; //zwiększamy wartość o val dla 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
	}
}
//wyznaczenie wartości w punkcie o indeksie n w czasie O(log)
int query(int n)
{
	n+=M; //właściwe ustawienie indeksu elementu przedziału 
	int w = 0; 
	while(n > 0) //dopóki nie znajdziemy się w korzeniu
	{
		w+=tab[n];
		n>>=1;
	}
	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;
	cin>>a>>q;

	M = 1; 
	while(M<=a) 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*2;i++) tab[i]=0;
	
	while(q--)
	{
		cin>>option;

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