Հատվածներով ծառ (Segment Tree)
TODO: ավելի մանրամասն segtree բացատրություն
Հատվածներով ծառը (Segment Tree) հանդիսանում է бинар ծառի վրա հիմնված տվյալների կառուցվածք, որն արտացոլում է տրված զանգվածn (array) կամ տարրերի ցանկը: Ծառի յուրաքանչյուր հանգույց (node) ներկայացնում է սկզբնական զանգվածի որևէ հատված (subarray):
Հատվածներով ծառում արմատային հանգույցը (root) ներկայացնում է ամբողջ զանգվածը, իսկ տերևային հանգույցները (leaves) ցույց են տալիս զանգվածի առանձին տարրերը: Միջանկյալ (internal) հանգույցները համապատասխան հատվածներ են, որոնք առաջանում են զանգվածը միմյանց հաջորդող մասերի բաժանելու միջոցով:
Սովորաբար, եթե որևէ հանգույց ներկայացնում է [l, r] ենթատարբերակը, ապա դրա ձախ զավակը (child) ցույց է տալիս [l, (l+r)/2] միջակայքը, իսկ աջ զավակը՝ [(l+r)/2 + 1, r]: Այս ռեկուրսիվ բաժանումը շարունակվում է այնքան ժամանակ, մինչև յուրաքանչյուր տերևային հանգույց ներկայացնի միայն մեկ տարր:
Հատվածներով ծառի յուրաքանչյուր հանգույցում պահվող արժեքը կախված է այն խնդիրից (query) կամ խնդրանքից, որը մեզ հետաքրքրում է: Ընդհանուր դեպքում, հաճախ կիրառվում է այս ծառը մասաղ суммы (sum), նվազագույնի (min), առավելագույնի (max) կամ որևէ այլ միացման գործողության (aggregate function) համար: Հանգույցի արժեքը հաշվարկվում է, ելնելով դրա զավակների արժեքներից:
Հատվածներով ծառը առանձնապես օգտակար է այն խնդիրներում, որոնք պահանջում են արագ հատվածային հարցումներ (range queries) և թարմացումներ (updates) զանգվածի վրա: Ծառի կառուցմամբ կարելի է կատարողել այդ գործողությունները O(log N) բարդության ժամանակում, որտեղ N-ն զանգվածի չափն է:
Ընդհանուր առմամբ, Հատվածներով ծառը (Segment Tree) հնարավորություն է տալիս զգալիորեն հեշտացնել հատվածային գործողությունները զանգվածների վրա, ապահովելով հարցումների և թարմացումների արդյունավետ իրականացում: Այն օգտագործվում է տարաբնույթ ալգորիթմներում (օրինակ, միջակայքային հարցումներ, հատվածային թարմացումներ և այլն):
Առաջադրանք: Հատվածներով ծառի հանգույցների իտերացիոն հաշվարկ
Ձեզ տրված է
n տարրերով զանգված: Ձեր խնդիրն է իտերացիոն ձևով կառուցել հատվածներով ծառը և հաշվարկել ծառի յուրաքանչյուր հանգույցի արժեքը: Յուրաքանչյուր հանգույցի արժեքը համապատասխանում է նրա նկարագրած ենթատարբերակի գումարին:Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 100 000), որը ցույց է տալիս զանգվածի տարրերի քանակը:Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր (), որոնք ներկայացնում են զանգվածի տարրերը:Ելք
Պետք է տպել հատվածներով ծառը (Segment Tree)՝ պահված բոլոր հանգույցների արժեքներով: Ծառի յուրաքանչյուր մակարդակը տպեք առանձին տողով, արժեքները բաժանելով բացատով:
Օրինակներ
Մուտք | Ելք |
4
1 2 3 4 | 10
3 7
1 2 3 4 |
8
3 7 9 6 2 1 5 4 | 37
25 12
10 15 3 9
3 7 9 6 2 1 5 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 10 MB