Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### daihan's blog

By daihan, 2 years ago, ,

You are given an array of size N , then you are given N integers A[i] = i'th element .

You will have to process some query , Q . Two types of query :

1 — that means print the maximum sub array sum in this array .

2 p V — Update the value of index p to V ;

Constraints:

1<=N<=9*10^4

1 ≤ Q ≤ 100000

How to solve it efficiently ? I got TLE in test 4 .

My code : https://ideone.com/GC3o8V

• -4

 » 2 years ago, # |   +4 simple segment tree with merging nodes
•  » » 2 years ago, # ^ |   0 Can you explain in details ?
•  » » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 This problem can be solved using a segment tree.To understand the solution, you can try to find the Maximum Sub Array Sum in a recursive divide & conquer approach. Once you have a d&c solution (that should have linear time), we can use that to mantain a segmentree containing all the needed information for each interval.Hint : you might also need to save information about prefix/suffix of the interval you are recurring on :)
 » 2 years ago, # | ← Rev. 2 →   +3 There is the same problem on SPOJThere is my solution1) Use Segment Tree (if you don't know it, solve some easy problems on segment tree previously)2) Each node of the Segment Tree will contain 4 numbers:sum — sum of all numbers of this segmentmaxprefix — maximum sum of the prefix on this segmentmaxsuffix — maximum sum of the suffix on this segmentmaxsum — maximum sibarray sum on this segmentCombine function will be easy:1) sum = left.sum + right.sum2) maxprefix = max(left.maxprefix, left.sum+right.maxprefix)3) maxsuffix = max(left.maxsuffix + right.sum, right.maxsuffix)4) maxsum = max(left.maxsum, right.maxsum, left.suffix+right.prefix)
•  » » 5 weeks ago, # ^ |   -6 why use 1000000007 as INF?