# 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?

# Introduction

I have come up with a more efficient solution in terms of the time complexity, although it's still not passing all the test cases. Nevertheless, I decided to post the solution, because it may help someone with a similar problem in the future.

# Explanation

The idea is to divide an initial array into segments of size √n, and for each segment to pre-calculate 4 helper arrays - sum of elements, minimum sum of elements, minimum prefix sum (minimum sum starting from the first element of the bucket) and minimum suffix sum (minimum sum ending at the last element of the bucket).

In such case, there are 3 possible use cases when calculating the min sum:

1. Sum range is within the same bucket. Then, to calculate the minimum subsum there, do it brute force.

2. Sum range starts in one bucket and ends in a neighbouring bucket. Again, do brute force.

3. Sum range covers more than 2 buckets. That's the hardest case, and that's what for all the additional arrays are built. The minimum sum in the range can happen to be a minimum subsum in some bucket, or a minimum prefix, or a suffix, or a sum of the min suffix and prefix (both buckets are in the range), or a sum of all elements in the current bucket and "special" sum from previous matching buckets. The "special" sum is either a min suffix from the preceding matching bucket or sum of elements starting from some min suffix. Please see the code for more details.

When a value is updated, all 4 helper arrays have to be updated too, and that is done in O(√n) time.

# Code

import math
import sys

class MinSumRangeQuery:
size = None
array = None

bucket_size = None
bucket_sums = None
min_prefix_sums = None
min_suffix_sums = None
min_subarray_sums = None

def __init__(self, array):
self.size = len(array)
self.array = array

self.bucket_size = int(math.sqrt(self.size))
self.bucket_sums = [None] * (self.bucket_size)
self.min_prefix_sums = [None] * (self.bucket_size)
self.min_suffix_sums = [None] * (self.bucket_size)
self.min_subarray_sums = [None] * (self.bucket_size)

left = 0
for i in range(self.bucket_size):
right = left + self.bucket_size

# sum of elements in a bucket
self.bucket_sums[i] = sum(self.array[left:right])
# calculate a min sum starting from the left position
self.min_prefix_sums[i] = self.find_min_prefix(left, right)
# calculate a min sum ending at the right position
self.min_suffix_sums[i] = self.find_min_suffix(left, right)
# calculate a min sum within the bucket
self.min_subarray_sums[i] = self.find_min_subsum(left, right)
left += self.bucket_size

def find_min_prefix(self, left, right):
min_prefix = self.array[left]
current_prefix = min_prefix
for i in range(left + 1, right):
current_prefix += self.array[i]
if current_prefix < min_prefix:
min_prefix = current_prefix

return min_prefix

def find_min_suffix(self, left, right):
min_suffix = self.array[right - 1]
current_suffix = min_suffix
for i in range(right - 2, left - 1, -1):
current_suffix += self.array[i]
if current_suffix < min_suffix:
min_suffix = current_suffix

return min_suffix

def find_min_subsum(self, left, right):
current_min_subsum = 0
min_subsum = sys.maxsize

for i in range(left, right):
current_min_subsum = min(current_min_subsum + self.array[i],
self.array[i])
if current_min_subsum < min_subsum:
min_subsum = current_min_subsum

return min_subsum

def find_min_in_range(self, left, right):
current_bucket_id = int(left / self.bucket_size)
end_bucket_id = int(right / self.bucket_size)
current_right = min((current_bucket_id + 1) * self.bucket_size, right)

current_min_subsum = self.find_min_suffix(left, current_right)
min_sum = self.find_min_subsum(left, current_right)

current_bucket_id += 1
while current_bucket_id < end_bucket_id:
min_prefix = self.min_prefix_sums[current_bucket_id]
min_subsum = self.min_subarray_sums[current_bucket_id]
min_suffix = self.min_suffix_sums[current_bucket_id]

min_sum = min(min_sum, min_prefix + current_min_subsum)
min_sum = min(min_subsum, min_sum)

current_min_subsum = min(current_min_subsum + self.bucket_sums[current_bucket_id],
min_suffix)
min_sum = min(current_min_subsum, min_sum)

current_bucket_id += 1

current_left = current_bucket_id * self.bucket_size
#if current_left < right:
min_prefix = self.find_min_prefix(current_left, right)
min_sum = min(current_min_subsum + min_prefix, min_sum)
min_sum = min(self.find_min_subsum(current_left, right), min_sum)

return min_sum

def update(self, index, value):
bucket_index = int(index / self.bucket_size)
if bucket_index < self.bucket_size:
self.bucket_sums[bucket_index] += (value - self.array[index])
self.array[index] = value
if bucket_index < self.bucket_size:
left = bucket_index * self.bucket_size
right = left + self.bucket_size
self.min_suffix_sums[bucket_index] = self.find_min_suffix(left, right)
self.min_prefix_sums[bucket_index] = self.find_min_prefix(left, right)
self.min_subarray_sums[bucket_index] = self.find_min_subsum(left, right)

tests = int(input())

for i in range(tests):
size = int(input())

array = [int(i) for i in input().split()]

minSumRangeQuery = MinSumRangeQuery(array)

queries = int(input())

for _ in range(queries):
a, x, y = [int(i) for i in input().split()]
x -= 1

if a == 1:
print(minSumRangeQuery.find_min_in_range(x, y))
elif a == 0 and array[x] != y:
minSumRangeQuery.update(x, y)


# Algorithm Complexity

Time complexity of the algorithm is O(n√n), and space complexity is O(√n) because 4 arrays for each bucket have to be maintained.