Problem Statement
Starting with a 1indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
Example:
$n=10\queries = [[1,5,3],[4,8,7],[6,9,1]]$
Queries are interpreted as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of $k$ between the indices $a$ and $b$ inclusive:
index> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]
The larges values is $10$ after all operation are performed.
Solution
Brute Force
 Create array with length
n+1
to simplify update result  For each queries sum index range from
a
tob
with values ofk
 Find max values
func arrayManipulation(n int32, queries [][]int32) int64 {
result:=make([]int64, n+1)
for _, q:= range queries{
for from:=q[0];from<=q[1];from++{
result[from]+=int64(q[2])
}
}
// fmt.Println(result)
max:=int64(1)
for _,q:= range result{
if max < q{
max = q
}
}
return int64(max)
}
This solution works well with small data test, but got time limit exceeded with the data growing big because we must iterate from a
to b
every query.
Prefixsum^{1}
 The process starts by initializing an array of size n with all zeros. Then, the function processes each query in the twodimensional array of queries. Each query is a triplet of integers (a, b, k) that represents adding the value k to all elements in the range [a, b] of the array arr.
 To perform this operation efficiently, the function uses the technique of prefix sums^{1} (cumulative sums), where each element of the array represents the difference between the current element and the previous one. This technique allows us to compute the sum of a range of elements in the array in constant time.
 After processing all the queries, the function loops through the array and computes the maximum value by keeping track of the running sum of the array elements. The maximum value is updated whenever the running sum exceeds the current maximum.
func arrayManipulation(n int32, queries [][]int32) int64 {
arr := make([]int64, n)
for _, q := range queries {
a, b, k := q[0], q[1], q[2]
arr[a1] += int64(k)
if b < n {
arr[b] = int64(k)
}
}
max := int64(0)
sum := int64(0)
for _, val := range arr {
sum += val
if sum > max {
max = sum
}
}
return max
}
Dry Run
 Sample Input
5 3
1 2 100
2 5 100
3 4 100

initial array:
[ 0, 0, 0, 0, 0]

q[0], 1 2 100
:[ 100, 0,100, 0, 0]

q[1], 2 5 100
:[ 100, 100,100, 0, 0]
, add100
skipped becauseb
is same withn

q[3], 3 4 100
:[ 100, 100, 0, 0,100]

find the max values from current sum
 index
0
:sum = 100, max = 100
, max updated  index
1
:sum = 200, max = 200
, max updated  index
2
:sum = 200, max = 200
 index
3
:sum = 200, max = 200
 index
4
:sum = 100, max = 200
 index

final result is $200$