算法设计：最大和连续子数组的范围查询

2021年5月16日17:10:49 发表评论 892 次浏览

本文概述

给定数量为N和Q的两种类型1和2的查询。任务是为给定查询编写代码, 其中在类型1中给定的l和r, 任务是打印最大和连续子数组对于类型2, 给定类型, 索引和值, 将值更新为A编号.

例子 ：

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 : Answer to 1st query : 6 
Answer to 3rd query : 11

说明：在第一个查询中, 任务是打印范围为5-8的连续子数组的最大和, 该子数组由{-2, 1, 5, -3}组成。最大和为6, 由子数组{1, 5}形成。在第二个查询中, 执行了更新操作, 该操作将a [1]更新为10, 因此序列为{10, -3, 4, -1, -2, 1, 5, -3}。在第三个查询中, 任务是打印范围为1-3的连续子数组的最大和, 该子数组由{10, -3, 4}组成。最大和为11, 由子数组{10, -3, 4}组成。

一种简单的方法用于Kadane的算法对于每个类型1查询。每个类型1查询的复杂度为O(n)。类型2查询在O(1)中完成。

高效方法：

一种有效的方法是构建一个分段树, 其中每个节点存储四个值(总和, 前缀总和, 后缀总和, 最大总和), 并对其进行范围查询以找到每个查询的答案。段树的节点如上所述存储四个值。父母将存储左右孩子的合并。父节点存储值, 如下所述：

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 =最大值(parent.prefixsum, parent.suffixsum, left.maxsum, right.maxsum, left.suffixsum + right.prefixsum)

父节点存储以下内容：

  • 父节点的总和是左右子总和的总和。
  • 父节点的前缀总和将等于左侧孩子的前缀总和或左侧孩子的总和+右侧孩子前缀的总和。
  • 父节点的后缀总和等于右子后缀总和或右子后缀+左子后缀总和
  • 父节点的maxsum将是父级的prefixsum或后缀和的最大值, 或左或右子级的maxsum或左子级的后缀和右子级的prefixsum的总和。

段树的表示形式：

1.叶节点是输入数组的元素。

2.每个内部节点代表叶节点的一些合并。对于不同的问题, 合并可能会有所不同。对于此问题, 如上所述进行合并。

树的数组表示形式用于表示段树。对于索引i处的每个节点, 左子节点在索引处2 *我+ 1, 合适的孩子在2 *我+ 2父母在(i – 1)/ 2.

从给定数组构造细分树：

从段arr [0开始。 。 。 n-1]。然后每次将当前段分成两半(如果尚未变成长度为1的段), 然后在两个半段上调用相同的过程, 对于每个这样的段, 将值存储在给定的所有四个变量中在上面的公式中。

更新数组和段Tree中的给定值：

从提供给我们的阵列的完整部分开始。每次将数组分成两半

忽略不存在要更新的索引的一半

。继续忽略每一步, 直到到达叶子节点为止, 在该叶子节点处将值更新为给定索引。现在, 根据给定的公式将更新的值合并到我们遍历的路径中存在的所有节点。

回答查询：

对于每个查询, 请移至树的左右两半。只要给定范围完全与树的任何一半重叠, 就从那一半返回Node, 而无需在该区域中进一步遍历。当一半的树完全位于给定范围之外时, 返回INT_MIN。范围部分重叠时, 左右移动一半, 然后相应地返回。

下面是上述想法的实现：

C ++

//CPP 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);
  
         //maxum 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);
  
         //maxum 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);
  
         //maxum 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);
  
         //maxum 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)
  
         # maxum 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)
  
         # maxum 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);
  
         //maxum 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);
  
         //maxum 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

输出如下：

6
11

时间复杂度：O(n log n)用于构建树, O(log n)用于每个类型1查询, O(1)用于类型2查询。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: