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

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

## 本文概述

``````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``````

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.每个内部节点代表叶节点的一些合并。对于不同的问题, 合并可能会有所不同。对于此问题, 如上所述进行合并。

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

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