Range query for Largest Sum Contiguous Subarray
Given an array a[] of size N, and Q queries of two types 1 and 2. For the given query of:
- Type 1: given l and r (they are positions), and task is to print the Largest sum Contiguous Subarray
- Type 2: given type, index, and value, update aindex = value.
Examples:
Input: a[] = {-2, -3, 4, -1, -2, 1, 5, -3}
1st query : 1 5 8
2nd query : 2 1 10
3rd query : 1 1 3
Output: 6, 11
Explanation: Initially the array from position 5 to 8 is {-2, 1, 5, -3}
The largest sum contiguous subarray = {1, 5}. Sum = 6
After updating a[1] = 10, array is {10, -3, 4, -1, -2, 1, 5, -3}
The largest sum contiguous subarray from 1 to 3 is {10, -3, 4}.
The sum is 11.
Naive approach: The simplest idea is to use Kadane’s algorithm for every type-1 query. The complexity of every type-1 query is O(N) and the type-2 query can be done in constant time
Time Complexity: O(N*Q)
Auxiliary Space: O(1)
Largest Sum Contiguous Subarray using Segment Tree:
An efficient approach is to build a segment tree where each node stores four values (sum, prefixsum, suffixsum, maxsum), and do a range query on it to find the answer to every query. The parent of a node will store the merging of left and right child.
The parent node stores the value as mentioned below :
parent_sum = left_sum + right_sum
parent_prefixsum = max(left_prefixsum, left_sum + right_prefixsum)
parent_suffixsum = max(right_suffixsum, right_sum + left_suffixsum)
parent_maxsum = max(parent_prefixsum, parent_suffixsum, left_maxsum, right_maxsum, left_suffixsum + right_prefixsum)
This can be divided into the following stages
Representation of Segment trees :
- Leaf Nodes are the elements of the input array.
- Each internal node represents some merging of the leaf nodes. For this problem, merging is done as given above.
- An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2 * i + 1, right child at 2 * i + 2 and the parent is at (i – 1) / 2.
Construction of Segment Tree from given array:
- Start with a segment arr[0 . . . n-1]. and every time divide the current segment into two halves(if it has not yet become a segment of length 1).
- Then call the same procedure on both halves,
- For each such segment, store the values in all the four variables as given in the formulae above.
Update a given value in array and Segment Tree:
- Start with the complete segment of the array provided to us.
- Every time divide the array into two halves, ignore the half in which the index to be updated is not present.
- Keep on ignoring halves at every step until we reach the leaf node where the value should be updated,.
- Update the value to the given index.
- Now, merge the updated values according to the given formulae to all the nodes that are present in the path we have traversed.
Answering a query:
- For every query, move to the left and right halves of the tree.
- Whenever the given range completely overlaps any halve of a tree, return the Node from that half without traversing further in that region.
- When a halve of the tree completely lies outside the given range, return INT_MIN.
- On partial overlapping of range, traverse in left and right halves and return accordingly.
Below is the implementation of the above idea.
C++
// C++ program to find Largest Sum Contiguous // Subarray in a given range with updates #include <bits/stdc++.h> using namespace std; // Structure to store // 4 values that are to be stored // in the nodes struct node { int sum, prefixsum, suffixsum, maxsum; }; // array to store the segment tree node tree[4 * 100]; // function to build the tree void build(int arr[], int low, int high, int index) { // the leaf node if (low == high) { tree[index].sum = arr[low]; tree[index].prefixsum = arr[low]; tree[index].suffixsum = arr[low]; tree[index].maxsum = arr[low]; } else { int mid = (low + high) / 2; // left subtree build(arr, low, mid, 2 * index + 1); // right subtree build(arr, mid + 1, high, 2 * index + 2); // parent node's sum is the summation // of left and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to right // child suffix sum or right child sum + suffix // sum of left child tree[index].suffixsum = max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix of // parent or maximum of left child or right child // and summation of left child's suffix and right // child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to update the tree void update(int arr[], int index, int low, int high, int idx, int value) { // the node to be updated if (low == high) { tree[index].sum = value; tree[index].prefixsum = value; tree[index].suffixsum = value; tree[index].maxsum = value; } else { int mid = (low + high) / 2; // if node to be updated is in left subtree if (idx <= mid) update(arr, 2 * index + 1, low, mid, idx, value); // if node to be updated is in right subtree else update(arr, 2 * index + 2, mid + 1, high, idx, value); // parent node's sum is the summation of left // and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to right // child suffix sum or right child sum + suffix // sum of left child tree[index].suffixsum = max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix of // parent or maximum of left child or right child // and summation of left child's suffix and // right child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to return answer to every type-1 query node query(int arr[], int index, int low, int high, int l, int r) { // initially all the values are INT_MIN node result; result.sum = result.prefixsum = result.suffixsum = result.maxsum = INT_MIN; // range does not lies in this subtree if (r < low || high < l) return result; // complete overlap of range if (l <= low && high <= r) return tree[index]; int mid = (low + high) / 2; // right subtree if (l > mid) return query(arr, 2 * index + 2, mid + 1, high, l, r); // left subtree if (r <= mid) return query(arr, 2 * index + 1, low, mid, l, r); node left = query(arr, 2 * index + 1, low, mid, l, r); node right = query(arr, 2 * index + 2, mid + 1, high, l, r); // finding the maximum and returning it result.sum = left.sum + right.sum; result.prefixsum = max(left.prefixsum, left.sum + right.prefixsum); result.suffixsum = max(right.suffixsum, right.sum + left.suffixsum); result.maxsum = max( result.prefixsum, max(result.suffixsum, max(left.maxsum, max(right.maxsum, left.suffixsum + right.prefixsum)))); return result; } // Driver Code int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // build the tree build(a, 0, n - 1, 0); // 1st query type-1 int l = 5, r = 8; cout << query(a, 0, 0, n - 1, l - 1, r - 1).maxsum; cout << endl; // 2nd type-2 query int index = 1; int value = 10; a[index - 1] = value; update(a, 0, 0, n - 1, index - 1, value); // 3rd type-1 query l = 1, r = 3; cout << query(a, 0, 0, n - 1, l - 1, r - 1).maxsum; return 0; }
Java
// Java program to find Largest Sum Contiguous // Subarray in a given range with updates class GFG { // Structure to store 4 values that are // to be stored in the nodes static class node { int sum, prefixsum, suffixsum, maxsum; }; // array to store the segment tree static node[] tree = new node[4 * 100]; // function to build the tree static void build(int arr[], int low, int high, int index) { // the leaf node if (low == high) { tree[index].sum = arr[low]; tree[index].prefixsum = arr[low]; tree[index].suffixsum = arr[low]; tree[index].maxsum = arr[low]; } else { int mid = (low + high) / 2; // left subtree build(arr, low, mid, 2 * index + 1); // right subtree build(arr, mid + 1, high, 2 * index + 2); // parent node's sum is the summation // of left and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to // right child suffix sum or right child sum + // suffix sum of left child tree[index].suffixsum = Math.max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix // of parent or maximum of left child or right // child and summation of left child's suffix // and right child's prefix. tree[index].maxsum = Math.max( tree[index].prefixsum, Math.max( tree[index].suffixsum, Math.max( tree[2 * index + 1].maxsum, Math.max( tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to update the tree static void update(int arr[], int index, int low, int high, int idx, int value) { // the node to be updated if (low == high) { tree[index].sum = value; tree[index].prefixsum = value; tree[index].suffixsum = value; tree[index].maxsum = value; } else { int mid = (low + high) / 2; // if node to be updated is in left subtree if (idx <= mid) { update(arr, 2 * index + 1, low, mid, idx, value); } // if node to be updated is in right subtree else { update(arr, 2 * index + 2, mid + 1, high, idx, value); } // parent node's sum is the summation of left // and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to // right child suffix sum or right child sum + // suffix sum of left child tree[index].suffixsum = Math.max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix // of parent or maximum of left child or right // child and summation of left child's suffix // and right child's prefix. tree[index].maxsum = Math.max( tree[index].prefixsum, Math.max( tree[index].suffixsum, Math.max( tree[2 * index + 1].maxsum, Math.max( tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to return answer to every type-1 query static node query(int arr[], int index, int low, int high, int l, int r) { // initially all the values are Integer.MIN_VALUE node result = new node(); result.sum = result.prefixsum = result.suffixsum = result.maxsum = Integer.MIN_VALUE; // range does not lies in this subtree if (r < low || high < l) { return result; } // complete overlap of range if (l <= low && high <= r) { return tree[index]; } int mid = (low + high) / 2; // right subtree if (l > mid) { return query(arr, 2 * index + 2, mid + 1, high, l, r); } // left subtree if (r <= mid) { return query(arr, 2 * index + 1, low, mid, l, r); } node left = query(arr, 2 * index + 1, low, mid, l, r); node right = query(arr, 2 * index + 2, mid + 1, high, l, r); // finding the maximum and returning it result.sum = left.sum + right.sum; result.prefixsum = Math.max( left.prefixsum, left.sum + right.prefixsum); result.suffixsum = Math.max( right.suffixsum, right.sum + left.suffixsum); result.maxsum = Math.max( result.prefixsum, Math.max( result.suffixsum, Math.max(left.maxsum, Math.max(right.maxsum, left.suffixsum + right.prefixsum)))); return result; } // Driver Code public static void main(String[] args) { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = a.length; for (int i = 0; i < 4 * 100; i++) { tree[i] = new node(); } // build the tree build(a, 0, n - 1, 0); // 1st query type-1 int l = 5, r = 8; System.out.print( query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); System.out.println(); // 2nd type-2 query int index = 1; int value = 10; a[index - 1] = value; update(a, 0, 0, n - 1, index - 1, value); // 3rd type-1 query l = 1; r = 3; System.out.print( query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); } } // This code is contributed by 29AjayKumar
Python3
# Python program to find Largest Sum Contiguous # Subarray in a given range with updates from sys import maxsize INT_MIN = -maxsize # Structure to store # 4 values that are to be stored # in the nodes class node: def __init__(self): self.sum = 0 self.prefixsum = 0 self.suffixsum = 0 self.maxsum = 0 # array to store the segment tree tree = [0] * (4 * 100) for i in range(4 * 100): tree[i] = node() def build(arr: list, low: int, high: int, index: int): global tree # the leaf node if low == high: tree[index].sum = arr[low] tree[index].prefixsum = arr[low] tree[index].suffixsum = arr[low] tree[index].maxsum = arr[low] else: mid = (low + high) >> 1 # left subtree build(arr, low, mid, 2 * index + 1) # right subtree build(arr, mid + 1, high, 2 * index + 2) # parent node's sum is the summation # of left and right child tree[index].sum = tree[2 * index + 1].sum + \ tree[2 * index + 2].sum # parent node's prefix sum will be equivalent # to maximum of left child's prefix sum or left # child sum + right child prefix sum. tree[index].prefixsum = max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum) # parent node's suffix sum will be equal to right # child suffix sum or right child sum + suffix # sum of left child tree[index].suffixsum = max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum) # maximum will be the maximum of prefix, suffix of # parent or maximum of left child or right child # and summation of left child's suffix and right # child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))) # function to update the tree def update(arr: list, index: int, low: int, high: int, idx: int, value: int): global tree # the node to be updated if low == high: tree[index].sum = value tree[index].prefixsum = value tree[index].suffixsum = value tree[index].maxsum = value else: mid = (low + high) >> 1 # if node to be updated is in left subtree if idx <= mid: update(arr, 2 * index + 1, low, mid, idx, value) # if node to be updated is in right subtree else: update(arr, 2 * index + 2, mid + 1, high, idx, value) # parent node's sum is the summation of left # and right child tree[index].sum = tree[2 * index + 1].sum + \ tree[2 * index + 2].sum # parent node's prefix sum will be equivalent # to maximum of left child's prefix sum or left # child sum + right child prefix sum. tree[index].prefixsum = max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum) # parent node's suffix sum will be equal to right # child suffix sum or right child sum + suffix # sum of left child tree[index].suffixsum = max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum) # maximum will be the maximum of prefix, suffix of # parent or maximum of left child or right child # and summation of left child's suffix and # right child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))) # function to return answer to every type-1 query def query(arr: list, index: int, low: int, high: int, l: int, r: int) -> node: # initially all the values are INT_MIN result = node() result.sum = result.prefixsum = result.\ suffixsum = result.maxsum = INT_MIN # range does not lies in this subtree if r < low or high < l: return result # complete overlap of range if l <= low and high <= r: return tree[index] mid = (low + high) >> 1 # right subtree if l > mid: return query(arr, 2 * index + 2, mid + 1, high, l, r) # left subtree if r <= mid: return query(arr, 2 * index + 1, low, mid, l, r) left = query(arr, 2 * index + 1, low, mid, l, r) right = query(arr, 2 * index + 2, mid + 1, high, l, r) # finding the maximum and returning it result.sum = left.sum + right.sum result.prefixsum = max(left.prefixsum, left.sum + right.prefixsum) result.suffixsum = max(right.suffixsum, right.sum + left.suffixsum) result.maxsum = max(result.prefixsum, max(result.suffixsum, max(left.maxsum, max(right.maxsum, left.suffixsum + right.prefixsum)))) return result # Driver Code if __name__ == "__main__": a = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(a) # build the tree build(a, 0, n - 1, 0) # 1st query type-1 l = 5 r = 8 print(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum) # 2nd type-2 query index = 1 value = 10 a[index - 1] = value update(a, 0, 0, n - 1, index - 1, value) # 3rd type-1 query l = 1 r = 3 print(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum) # This code is contributed by # sanjeev2552
C#
// C# program to find Largest Sum Contiguous // Subarray in a given range with updates using System; using System.Collections.Generic; class GFG { // Structure to store 4 values that are // to be stored in the nodes public class node { public int sum, prefixsum, suffixsum, maxsum; }; // array to store the segment tree static node[] tree = new node[4 * 100]; // function to build the tree static void build(int[] arr, int low, int high, int index) { // the leaf node if (low == high) { tree[index].sum = arr[low]; tree[index].prefixsum = arr[low]; tree[index].suffixsum = arr[low]; tree[index].maxsum = arr[low]; } else { int mid = (low + high) / 2; // left subtree build(arr, low, mid, 2 * index + 1); // right subtree build(arr, mid + 1, high, 2 * index + 2); // parent node's sum is the summation // of left and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.Max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to // right child suffix sum or right child sum + // suffix sum of left child tree[index].suffixsum = Math.Max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix // of parent or maximum of left child or right // child and summation of left child's suffix // and right child's prefix. tree[index].maxsum = Math.Max( tree[index].prefixsum, Math.Max( tree[index].suffixsum, Math.Max( tree[2 * index + 1].maxsum, Math.Max( tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to update the tree static void update(int[] arr, int index, int low, int high, int idx, int value) { // the node to be updated if (low == high) { tree[index].sum = value; tree[index].prefixsum = value; tree[index].suffixsum = value; tree[index].maxsum = value; } else { int mid = (low + high) / 2; // if node to be updated is in left subtree if (idx <= mid) { update(arr, 2 * index + 1, low, mid, idx, value); } // if node to be updated is in right subtree else { update(arr, 2 * index + 2, mid + 1, high, idx, value); } // parent node's sum is the summation of left // and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.Max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // parent node's suffix sum will be equal to // right child suffix sum or right child sum + // suffix sum of left child tree[index].suffixsum = Math.Max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix // of parent or maximum of left child or right // child and summation of left child's suffix // and right child's prefix. tree[index].maxsum = Math.Max( tree[index].prefixsum, Math.Max( tree[index].suffixsum, Math.Max( tree[2 * index + 1].maxsum, Math.Max( tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2] .prefixsum)))); } } // function to return answer to every type-1 query static node query(int[] arr, int index, int low, int high, int l, int r) { // initially all the values are int.MinValue node result = new node(); result.sum = result.prefixsum = result.suffixsum = result.maxsum = int.MinValue; // range does not lies in this subtree if (r < low || high < l) { return result; } // complete overlap of range if (l <= low && high <= r) { return tree[index]; } int mid = (low + high) / 2; // right subtree if (l > mid) { return query(arr, 2 * index + 2, mid + 1, high, l, r); } // left subtree if (r <= mid) { return query(arr, 2 * index + 1, low, mid, l, r); } node left = query(arr, 2 * index + 1, low, mid, l, r); node right = query(arr, 2 * index + 2, mid + 1, high, l, r); // finding the maximum and returning it result.sum = left.sum + right.sum; result.prefixsum = Math.Max( left.prefixsum, left.sum + right.prefixsum); result.suffixsum = Math.Max( right.suffixsum, right.sum + left.suffixsum); result.maxsum = Math.Max( result.prefixsum, Math.Max( result.suffixsum, Math.Max(left.maxsum, Math.Max(right.maxsum, left.suffixsum + right.prefixsum)))); return result; } // Driver Code public static void Main(String[] args) { int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = a.Length; for (int i = 0; i < 4 * 100; i++) { tree[i] = new node(); } // build the tree build(a, 0, n - 1, 0); // 1st query type-1 int l = 5, r = 8; Console.Write( query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); Console.WriteLine(); // 2nd type-2 query int index = 1; int value = 10; a[index - 1] = value; update(a, 0, 0, n - 1, index - 1, value); // 3rd type-1 query l = 1; r = 3; Console.Write( query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to find Largest Sum // Contiguous Subarray in a given range // with updates // Structure to store 4 values that are // to be stored in the nodes class node { constructor() { this.sum = 0; this.prefixsum = 0; this.suffixsum = 0; this.maxsum = 0; } }; // Array to store the segment tree var tree = Array(4 * 100).fill(new node()); // Function to build the tree function build(arr, low, high, index) { // The leaf node if (low == high) { tree[index].sum = arr[low]; tree[index].prefixsum = arr[low]; tree[index].suffixsum = arr[low]; tree[index].maxsum = arr[low]; } else { var mid = parseInt((low + high) / 2); // Left subtree build(arr, low, mid, 2 * index + 1); // Right subtree build(arr, mid + 1, high, 2 * index + 2); // Parent node's sum is the summation // of left and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // Parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // Parent node's suffix sum will be equal to right // child suffix sum or right child sum + suffix // sum of left child tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix of // parent or maximum of left child or right child // and summation of left child's suffix and right // child's prefix. tree[index].maxsum = Math.max(tree[index].prefixsum, Math.max(tree[index].suffixsum, Math.max(tree[2 * index + 1].maxsum, Math.max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))); } } // Function to update the tree function update(arr, index, low, high, idx, value) { // The node to be updated if (low == high) { tree[index].sum = value; tree[index].prefixsum = value; tree[index].suffixsum = value; tree[index].maxsum = value; } else { var mid = parseInt((low + high) / 2); // If node to be updated is in left subtree if (idx <= mid) { update(arr, 2 * index + 1, low, mid, idx, value); } // If node to be updated is in right subtree else { update(arr, 2 * index + 2, mid + 1, high, idx, value); } // Parent node's sum is the summation of left // and right child tree[index].sum = tree[2 * index + 1].sum + tree[2 * index + 2].sum; // Parent node's prefix sum will be equivalent // to maximum of left child's prefix sum or left // child sum + right child prefix sum. tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum); // Parent node's suffix sum will be equal to right // child suffix sum or right child sum + suffix // sum of left child tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum); // maximum will be the maximum of prefix, suffix of // parent or maximum of left child or right child // and summation of left child's suffix and // right child's prefix. tree[index].maxsum = Math.max(tree[index].prefixsum, Math.max(tree[index].suffixsum, Math.max(tree[2 * index + 1].maxsum, Math.max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))); } } // Function to return answer to every type-1 query function query(arr, index, low, high, l, r) { // Initially all the values are int.MinValue var result = new node(); result.sum = result.prefixsum = result.suffixsum = result.maxsum = -1000000000; // Range does not lies in this subtree if (r < low || high < l) { return result; } // Complete overlap of range if (l <= low && high <= r) { return tree[index]; } var mid = parseInt((low + high) / 2); // Right subtree if (l > mid) { return query(arr, 2 * index + 2, mid + 1, high, l, r); } // Left subtree if (r <= mid) { return query(arr, 2 * index + 1, low, mid, l, r); } var left = query(arr, 2 * index + 1, low, mid, l, r); var right = query(arr, 2 * index + 2, mid + 1, high, l, r); // Finding the maximum and returning it result.sum = left.sum + right.sum; result.prefixsum = Math.max(left.prefixsum, left.sum + right.prefixsum); result.suffixsum = Math.max(right.suffixsum, right.sum + left.suffixsum); result.maxsum = Math.max(result.prefixsum, Math.max(result.suffixsum, Math.max(left.maxsum, Math.max(right.maxsum, left.suffixsum + right.prefixsum)))); return result; } // Driver Code var a = [ -2, -3, 4, -1, -2, 1, 5, -3 ]; var n = a.length; for(var i = 0; i < 4 * 100; i++) { tree[i] = new node(); } // Build the tree build(a, 0, n - 1, 0); // 1st query type-1 var l = 5, r = 8; document.write(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); document.write("<br>"); // 2nd type-2 query var index = 1; var value = 10; a[index - 1] = value; update(a, 0, 0, n - 1, index - 1, value); // 3rd type-1 query l = 1; r = 3; document.write(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum); // This code is contributed by rrrtnx </script>
6 11
Time Complexity: O(N * logN)
- O(N ) For building the tree
- O(logN) for every type-1 query
- O(logN) for type-2 query.
Auxiliary Space: O(N)
Related Topic: Segment Tree
Contact Us