I was trying to solve a the question in Segment Tree section in Edu section (Segment Tree, Step2, Problem A (segment with maximum sum)) using iterative version of segment tree, but it's not working with it while the recursive version with the same logic works.↵
↵
Could anyone please help with this? I am unable to find out where I am mistaking.↵
↵
↵
↵
<spoiler summary="Code">↵
↵
import java.util.*;↵
import java.io.*;↵
↵
public class CFsolve2 {↵
↵
public static void main(String[] args) {↵
FastScanner input = new FastScanner();↵
PrintWriter out = new PrintWriter(System.out);↵
int n = input.nextInt();↵
int m = input.nextInt();↵
↵
long[]arr = new long[n];↵
Item[] seg = new Item[4*n];↵
↵
for(int i=0;i<n;i++){↵
arr[i] = input.nextInt();↵
//leaf node holds array elements in tree.↵
seg[i+n] = getItem(arr[i]);↵
}↵
↵
build(n, seg);↵
out.println(seg[1].ans);↵
↵
while(m-->0){↵
int i = input.nextInt();↵
int val = input.nextInt();↵
↵
//update value in array & segment tree↵
arr[i]=val;↵
seg[n+i] = getItem(val);↵
↵
//fix/update the tree (upwards, leaf to root)↵
update(seg, n+i);↵
out.println(seg[1].ans);↵
}↵
↵
out.close();↵
}↵
↵
static Item getItem(long val){↵
if(val>0)↵
return new Item(val,val,val,val);↵
return new Item(0,0,val,0);↵
}↵
↵
static void build(int n, Item[]seg){↵
for(int i=n-1; i>0; i--){↵
//same as merge(seg[2*i],seg[2*i+1])↵
seg[i] = merge(seg[i<<1], seg[i<<1|1]);↵
}↵
}↵
↵
static void update(Item[] seg, int i) {↵
while (i > 1) {↵
i >>>= 1;↵
seg[i] = merge(seg[i<<1], seg[i<<1|1]);↵
}↵
}↵
↵
↵
static Item merge(Item left, Item right){↵
↵
Item parent = new Item(0,0,0,0);↵
parent.sum = left.sum + right.sum;↵
parent.suf = myMax(right.suf, right.sum + left.suf);↵
parent.pref = myMax(left.pref, left.sum + right.pref);↵
parent.ans = myMax(left.ans, myMax(right.ans,left.suf + right.pref));↵
↵
return parent;↵
}↵
↵
↵
static class Item{↵
long suf,pref,sum,ans;↵
Item(long suf, long pref, long sum, long ans){↵
this.suf = suf;↵
this.pref = pref;↵
this.sum = sum;↵
this.ans = ans;↵
}↵
}↵
↵
static Item getItem(long val){↵
if(val>0)↵
return new Item(val,val,val,val);↵
return new Item(0,0,val,0);↵
}↵
↵
static long myMin(long l, long r){↵
return l<r?l:r;↵
}↵
static int myMin(int l, int r){↵
return l<r?l:r;↵
}↵
↵
static long myMax(long l, long r){↵
return l>r?l:r;↵
}↵
static int myMax(int l, int r){↵
return l>r?l:r;↵
}↵
↵
↵
↵
static class FastScanner {↵
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));↵
StringTokenizer st=new StringTokenizer("");↵
String next() {↵
while (!st.hasMoreTokens())↵
try {↵
st=new StringTokenizer(br.readLine());↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return st.nextToken();↵
}↵
↵
int nextInt() {↵
return Integer.parseInt(next());↵
}↵
int[] readArray(int n) {↵
int[] a=new int[n];↵
for (int i=0; i<n; i++) a[i]=nextInt();↵
return a;↵
}↵
byte nextByte(){↵
return Byte.parseByte(next());↵
}↵
long nextLong() {↵
return Long.parseLong(next());↵
}↵
}↵
}↵
↵
</spoiler>↵
static long myMax(long l, long r){↵
return l>r?l:r;↵
}↵
↵
My Output: ↵
5↵
11↵
8↵
↵
Correct Output:↵
8↵
11↵
7↵
↵
</spoiler>↵
↵
↵
Thanks.↵
↵
↵
Could anyone please help with this? I am unable to find out where I am mistaking.↵
↵
↵
import java.util.*;↵
import java.io.*;↵
↵
public class CFsolve2 {↵
↵
FastScanner input = new FastScanner();↵
PrintWriter out = new PrintWriter(System.out);↵
int n = input.nextInt();↵
int m = input.nextInt();↵
↵
long[]arr = new long[n];↵
Item[] seg = new Item[4*n];↵
↵
for(int i=0;i<n;i++){↵
arr[i] = input.nextInt();↵
//leaf node holds array elements in tree.↵
seg[i+n] = getItem(arr[i]);↵
}↵
↵
build(n, seg);↵
out.println(seg[1].ans);↵
↵
while(m-->0){↵
int i = input.nextInt();↵
int val = input.nextInt();↵
↵
//update value in array & segment tree↵
arr[i]=val;↵
seg[n+i] = getItem(val);↵
↵
//fix/update the tree (upwards, leaf to root)↵
update(seg, n+i);↵
out.println(seg[1].ans);↵
}↵
↵
out.close();↵
}↵
↵
static Item getItem(long val){↵
if(val>0)↵
return new Item(val,val,val,val);↵
return new Item(0,0,val,0);↵
}↵
↵
static void build(int n, Item[]seg){↵
for(int i=n-1; i>0; i--){↵
//same as merge(seg[2*i],seg[2*i+1])↵
seg[i] = merge(seg[i<<1], seg[i<<1|1]);↵
}↵
}↵
↵
static void update(Item[] seg, int i) {↵
while (i > 1) {↵
i >>>= 1;↵
seg[i] = merge(seg[i<<1], seg[i<<1|1]);↵
}↵
}↵
↵
↵
Item parent = new Item(0,0,0,0);↵
parent.sum = left.sum + right.sum;↵
parent.suf = myMax(right.suf, right.sum + left.suf);↵
parent.pref = myMax(left.pref, left.sum + right.pref);↵
parent.ans = myMax(left.ans, myMax(right.ans,left.suf + right.pref));↵
↵
return parent;↵
}↵
↵
↵
static class Item{↵
long suf,pref,sum,ans;↵
Item(long suf, long pref, long sum, long ans){↵
this.suf = suf;↵
this.pref = pref;↵
this.sum = sum;↵
this.ans = ans;↵
}↵
}↵
↵
if(val>0)↵
return new Item(val,val,val,val);↵
return new Item(0,0,val,0);↵
}↵
↵
static long myMin(long l, long r){↵
return l<r?l:r;↵
}↵
static int myMin(int l, int r){↵
return l<r?l:r;↵
}↵
↵
static long myMax(long l, long r){↵
return l>r?l:r;↵
}↵
static int myMax(int l, int r){↵
return l>r?l:r;↵
}↵
↵
↵
↵
static class FastScanner {↵
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));↵
StringTokenizer st=new StringTokenizer("");↵
String next() {↵
while (!st.hasMoreTokens())↵
try {↵
st=new StringTokenizer(br.readLine());↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return st.nextToken();↵
}↵
↵
int nextInt() {↵
return Integer.parseInt(next());↵
}↵
int[] readArray(int n) {↵
int[] a=new int[n];↵
for (int i=0; i<n; i++) a[i]=nextInt();↵
return a;↵
}↵
byte nextByte(){↵
return Byte.parseByte(next());↵
}↵
long nextLong() {↵
return Long.parseLong(next());↵
}↵
}↵
}↵
↵
</spoiler>
static long myMax(long l, long r){↵
return l>r?l:r;↵
}↵
↵
My Output: ↵
5↵
11↵
8↵
↵
Correct Output:↵
8↵
11↵
7↵
↵
</spoiler>↵
↵
↵
Thanks.↵
↵
