Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Paradeigma tou Segment Tree:
- Otan pianei to athrisma twn stoixeiwn
- Kai otan ginete update prosthetei kapio sigkekrimeno arithmo stis theseis
- Liga logia gia avto:
- To segment tree einai ena binary tree data strucure pou o kathe "komvos"
- apothikevkei mia geniki timi gia to interval pou einai ipevthino
- diladi an apothikevoume athrismata(paradeigma mas) tote o "komvos" pou en ipevthinos gia
- tin perioxi 1-8 xerei to athrisma twn stoixeiwn apo to 1 ws to 8
- Avto petyxenete apo to oti pernei tin pliroforia apo ta paidia tou(binary tree)
- opou to arsistero paidi eshi p tin arxi ws tin mesi (dld apothikevei to athrisma p to 1 ws 4)
- kai to dexi paidi eshi p tin mesi+1(gia na men iparxoun colisions) ws to telos(dld apothikevei to athrisma p to 5 ws 8)
- alla an einai fyllo dld exei tin pliroforia gia ena stoixeio aplos pianoume tin pliroforia p ton pinaka mas
- ston kodika einai: seg[cth]=pin[s];
- */
- #include<iostream>
- using namespace std;
- int pin[100000];///Pinakas me to data
- int seg[200010];///To segment tree mas
- int n;///To plithos twn stoixeiwn
- ///To recurence relation
- int rec(int a, int b)
- {
- ///Edw tha grafoume tin sxesi tou patera me ta paidia tou
- ///Sigkekrimena to pateras einai to athrisma twn 2 paidiwn
- ///Tha mporouse na einai to pio megalo apo ta 2
- ///tote tha stelname:
- ///return max(a, b);
- return a+b;
- }
- ///Gia arxikopoiisi tou Segment Tree
- ///s=>arxi t interval
- ///e=>telos t inetrval
- ///cth=> pou eimaste sto Segment Tree
- void reset(int s, int e, int cth)
- {
- ///Leaf Periptosi
- if(s==e)///Otan I arxi en ison tou telous
- {
- seg[cth]=0; ///midenizoume
- return; ///klinoume to maxazi
- }
- ///Oxi Leaf Periptosi
- int mid=(s+e)/2;///Vriskoume to middle
- reset(s, mid, cth*2);///pame sto aristero paidi
- reset(mid+1, e, cth*2+1);///pame sto dexi paidi
- ///To recurence relation!!!(stelnoume ta 2 paithkia)
- seg[cth]=rec(seg[cth*2], seg[cth*2+1]);
- return;///klinoume to maxazi
- }
- ///Gia na dwsoume times sto Segment Tree
- ///s=>arxi t interval
- ///e=>telos t inetrval
- ///cth=>pou eimaste sto Segment Tree
- void create(int s, int e, int cth)
- {
- ///Leaf Periptosi
- if(s==e)///Otan I arxi en ison tou telous
- {
- seg[cth]=pin[s];///Dioume stin akrea periptosi tin timi
- return;
- }
- int mid=(s+e)/2;///Vriskoume to middle
- create(s, mid, cth*2);///pame sto aristero paidi
- create(mid+1, e, cth*2+1);///pame sto dexi paidi
- ///To recurence relation!!!(stelnoume ta 2 paithkia)
- seg[cth]=rec(seg[cth*2], seg[cth*2+1]);
- return;
- }
- ///Otan theloume na antlisoume plirofories apo to segment tree
- ///ters=>arxi avtoy p theloume
- ///tere=>telos avtoy p theloume
- ///s=>arxi t interval
- ///e=>telos t inetrval
- ///cth=>pou eimaste sto Segment Tree
- int query(int ters, int tere, int s, int e, int cth)
- {
- ///an fkoume ektos oriwn
- if(tere<s || ters>e)
- {
- ///epistrefoume mia timi pou den tha mas epireasei
- ///px sto athrisma to 0
- return 0;
- }
- ///an o "komvos" en mes sta oreia mas
- if(ters<=s && e<=tere)
- {
- ///aplos stelnoume tin timi
- return seg[cth];
- }
- int mid=(s+e)/2;///Vriskoume to middle
- ///Pianoume pliroforia apo to aristero paidi
- int part1=query(ters, tere, s, mid, cth*2);
- ///Pianoume pliroforia apo to dexi paidi
- int part2=query(ters, tere, mid+1, e, cth*2+1);
- ///Epistrefoume to recurence relation
- return rec(part1, part2);
- }
- ///Otan theloume na ananeosoume plirofories apo to segment tree
- ///Edw aplos prosthetoume to num sta stoixeia
- ///ters=>arxi avtoy p theloume
- ///tere=>telos avtoy p theloume
- ///s=>arxi t interval
- ///e=>telos t inetrval
- ///num=>timi alagis
- ///cth=>pou eimaste sto Segment Tree
- void updall(int ters, int tere, int s, int e, int num, int cth)
- {
- ///an fkoume ektos oriwn
- if(tere<s || ters>e)
- {
- ///klinoume to maxazi
- return;
- }
- ///otan ftasoume se fyllo
- if(s==e)
- {
- ///aplos prothetoume
- seg[cth]+=num;
- ///klinoume to maxazi
- return;
- }
- int mid=(s+e)/2;///Vriskoume to middle
- ///kanoume update to aristero paidi
- updall(ters, tere, s, mid, num, cth*2);
- ///kanoume update to dexi paidi
- updall(ters, tere, mid+1, e, num, cth*2+1);
- ///To recurence relation!!!(stelnoume ta 2 paithkia)
- seg[cth]=rec(seg[cth*2], seg[cth*2+1]);
- return;///klinoume to maxazi
- }
- ///Ena paradeigma pws doulefkoun ta Functions
- int main()
- {
- int i;///Gia to for
- cin>>n;///Diavazoume ta stoixeia
- reset(1, n, 1);///midenizoume to segment tree
- ///diavazoume ta stoixeia
- for(i=1; i<=n; i++)
- cin>>pin[i];
- ///diavazoume ta stoixeia
- ///Dimiourgoume to segment tree
- create(1, n, 1);
- ///Typwnw to athrisma twn stoixeiwn 1->n
- cout<<query(1, n, 1, n, 1)<<"\n";
- ///Mexri tin mesi proisthetw 15 se kathe stoixeio
- updall(1, n/2, 1, n, 15, 1);
- ///kai thorw tin mageia pou egine ;)
- cout<<query(1, n, 1, n, 1)<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement