I've a big problem: Given N number *a[1],a[2],..,a[N]* and M queries. **(N,M <= 10^5)**

Each query, change a[v] to x, and find the maximum sum subsequence such that no two elements are adjacent.

Example: a = {1,1,1,1,1,1}

First query, change a[5] to 3, thus a = {1,1,1,1,3,1} -> the answer is 5 (choose a[1],a[3],a[5])

Second query, change a[2] to 4, thus a = {1,4,1,1,3,1} -> the answer is 7 (choose a[2],a[5])

And so on..

I think use DP to solve this problem, but the complexity is **O(N*M)** can't run with N,M <= 10^5.

Could you help me? Thanks all.

**UPD:** I've solved this problem, thanks for all.

To handle updates we will use a segment tree. Each node [

l;r] will contain the following:a_{r}is the last chosen element anda_{l}is the first chosen elementa_{r}is the last chosen element anda_{l + 1}is the first chosen elementa_{r - 1}is the last chosen element anda_{l}is the first chosen elementa_{r - 1}is the last chosen element anda_{l + 1}is the first chosen elementFor shorter notation I will use

f(i,j) as the answer if the first included element isa_{i}and the last isa_{j}. Then in other words in a node we will keepf(l,r),f(l+ 1,r),f(l,r- 1) andf(l+ 1,r- 1).Now the merging of two nodes can be done in constant time. Lets have two adjacent nodes (

L_{1},R_{1}) and (L_{2},R_{2}). The conditionsL_{1}≤R_{1}<L_{2}≤R_{2}andR_{1}+ 1 =L_{1}hold. Then the merged node will have:f(A,B) =max(f(A,R_{1}- 1) +f(L_{2}+ 1,B),f(A,R_{1}) +f(L_{2}+ 1,B),f(A,R_{1}- 1) +f(L_{2},B))Where the pair (

A,B) is being one of the (L_{1},R_{2}), (L_{1}+ 1,R_{2}), (L_{1},R_{2}- 1) or (L_{1}+ 1,R_{2}- 1).And now the update is done by simply updating a leaf's node and the nodes from it to the root resulting in complexity. The answer after each update will be the maximal of the 4 values for the root node.

PS:This solution works only if for everyi,a_{i}≥ 0.PS2:f(x,x+ 1) = 0 for everyxas we cannot chose 2 adjacent elements.Thanks a lot. I'll try to solve the problem with your idea.

yo this saved me big time during this leetcode contest

！

Same here.

Why is this the case? In any case, we can treat negative a[i] as just zero since it's always better to discard negative numbers. But the original solution seemed to work regardless of whether a[i] is positive or negative.