Range add queries (difference array)
Java
Hard
5 views
Problem Description
Task: start with zeros of size n. Each query (l,r,add) adds add to every index in [l,r]. Return final array.
Output Format
Return value
Constraints
Use long; O(n+q).
Official Solution
static long[] rangeAdd(int n,int[][] q){long[] diff=new long[n+1];for(int[] t:q){int l=t[0],r=t[1],add=t[2];diff[l]+=add;if(r+1<n) diff[r+1]-=add;}long[] res=new long[n];long cur=0;for(int i=0;i<n;i++){cur+=diff[i];res[i]=cur;}return res;}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!