本文概述

• C ++
• Java
• Python3
• C#

给定数量为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 toevery 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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 maxsizeINT_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 = https://www.lsbin.com/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 = https://www.lsbin.com/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查询。

推荐阅读

• 

  社保需要交多少年才可以领养老金?养老金是怎么算的
• 

  人造棉是棉绸吗
• 

  教你如何开挂，教你如何自己做挂不用担心被抓
• 

  老竹大方茶的产地及品质特征介绍
• 

  八小时工作制最早出现在哪个国家
• 

  故事里的人——石神与石泓
• 

  家里的小猫得了猫藓,医生照了一下说很严重开了八百多块钱药,请问这个花费正常吗,以后还要花多少钱？
• 

  锦鲤花养殖注意事项 锦鲤水花养殖注意事项
• 

  抖音朋友圈射箭穿心表白图制作教程
• 

  外用药能否治疗早泄 早泄的外用药
• 

  佳能5d拍摄技巧 佳能5ds拍体育
• 

  让龙猫亲近自己的方法有吗
• 

  重庆被起诉了但是实在没有钱还怎么办
• 

  科目4多少分才算合格
• 

  笔记|多线程基础
• 

  用户|为什么iQOO Z3能不让用户做“取舍”？
• 

  FGO情人节三期高难本怎么打 2019女帝情人节高难本攻略
• 

  一辈子闺蜜经典句子有哪些
• 

  大金空调制冷外机不工作怎么办,一般情况就放置在这个位置
• 

  如何搭建直播电商平台，如何做好电商直播平台

• 如何使用jQuery检查元素是否包含类（）
• 在链表中找到最大和第二大的值
• 为什么Python是最适合机器学习的编程语言（）
• 将数组的所有元素减少为零所需的最少步骤
• 密码学中的轻松密钥管理介绍
• 不含回文的最长子字符串的长度
• 使用Fenwick树在L到R范围内大于K的元素数（离线查询）
• Android自动化测试环境部署
• idea 导入 android项目