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.