# Given an integer array A and a range, find a subarray within the range with a minimum sum

## Problem

HackerRank Range query:

You are given an array A of n integers. You have to perform m queries on the array. The queries are of two types:

1. Modify the ith element of the array.

2. Given x, y, print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}.

Note: A brute force solution may not work; Try using an efficient data structure. Use fast I/O to avoid TLE.

### Input Format

The first line contains an integer t denoting the number of test cases.

The next line consists of an integer n.

The following line contains n integers representing the array A.

The next line contains an integer m denoting the number of queries.

The following m lines contain integers of the form given below.

• 0 x y: modify Ax into y
• 1 x y: print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}

### Constraints

1 ≤ t ≤ 100

1 ≤ n ≤ 50000

-10000 ≤ Ai ≤ 10000

0 ≤ m ≤ 50000

### Output Format

For each query print the output as specified.

## My Solution

### Algorithm

1. Calculate prefix sums prefix_sums for the given array.
2. For the given interval, move from left to right and keep track of the largest encountered value max_prefix_sum of prefix_sums and the minimum subsum min_subsum (min_subsum = min(prefix_sums[i] - max_prefix_sum) for left=<i<=right). In the end, min_subsum is the answer.
3. If some value of the initial array is updated then prefix_sums must be updated accordingly.

The overall time complexity of the algorithm is O(n2). The space complexity is O(n). I know that for a O(n2) time complexity solution I don't need any additional array and there's a more elegant solution for this based on Maximum Subarray Problem. However, it feels like with prefix sums I have a better chance of having a O(nlogn) or O(n1.5) time complexity solution.

### Code

import itertools

class MinSumRangeQuery:
prefix_sums = None

def __init__(self, array):
self.prefix_sums = list(itertools.accumulate(array))

def update(self, index, value):
diff = value - array[index]
for i in range(index, len(self.prefix_sums)):
self.prefix_sums[i] += diff

def min_subarray_sum(self, left, right):
if left == right:
return self.prefix_sums[left]

min_subsum = 99999999
max_prefix_sum = self.prefix_sums[left - 1]
for i in range(left, right + 1):
current_subsum = self.prefix_sums[i] - max_prefix_sum

if min_subsum > current_subsum:
min_subsum = current_subsum

if max_prefix_sum <= self.prefix_sums[i]:
max_prefix_sum = self.prefix_sums[i]

return min_subsum

for _ in range(int(input())):
n = int(input())
array = [int(i) for i in input().split()]
array.insert(0, 0)
minSumRangeQuery = MinSumRangeQuery(array)

for _ in range(int(input())):
a, x, y = [int(i) for i in input().split()]
if a == 1:
print(minSumRangeQuery.min_subarray_sum(x, y))
elif a == 0:
if array[x] != y:
minSumRangeQuery.update(x, y)


## Question

Given the constraints above, the code times out for all but a default test case. What's a more efficient way to solve the problem?