前缀和数组——竞争编程中的实现和应用-yiteyi-C++库

给定一个大小为n的数组arr[]，其前缀和数组是另一个大小相同的数组prefixSum[]，因此prefixSum[i]的值是arr[0]+arr[1]+arr[2]…arr[i]。

null

例如：

Input  : arr[] = {10, 20, 10, 5, 15}Output : prefixSum[] = {10, 30, 40, 45, 60}Explanation : While traversing the array, update the element by adding it with its previous element.prefixSum[0] = 10, prefixSum[1] = prefixSum[0] + arr[1] = 30, prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

为了填充前缀和数组，我们从索引1运行到last，并继续将当前元素与前缀和数组中的前一个值相加。以下是实施情况：

C++

                         // C++ program for Implementing                       
                         // prefix sum array                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Fills prefix sum array                       
                         void                                     fillPrefixSum(                                     int                                     arr[],                                     int                                     n,                                     int                                     prefixSum[])                       
                         {                       
                                                 prefixSum[0] = arr[0];                       
           
                                                 // Adding present element                       
                                                 // with previous element                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 prefixSum[i] = prefixSum[i - 1] + arr[i];                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 10, 4, 16, 20 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     prefixSum[n];                       
           
                                                 fillPrefixSum(arr, n, prefixSum);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << prefixSum[i] <<                                     " "                                     ;                       
                         }                       

JAVA

                         // Java Program for Implementing                       
                         // prefix sum arrayclass                       
                         class                                     Prefix {                       
                                                 // Fills prefix sum array                       
                                                 static                                     void                                     fillPrefixSum(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     prefixSum[])                       
                                                 {                       
                                                 prefixSum[                                     0                                     ] = arr[                                     0                                     ];                       
           
                                                 // Adding present element                       
                                                 // with previous element                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; ++i)                       
                                                 prefixSum[i] = prefixSum[i -                                     1                                     ] + arr[i];                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     10                                     ,                                     4                                     ,                                     16                                     ,                                     20                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     prefixSum[] =                                     new                                     int                                     [n];                       
           
                                                 fillPrefixSum(arr, n, prefixSum);                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 System.out.print(prefixSum[i] +                                     " "                                     );                       
                                                 System.out.println(                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         // This Code is Contributed by Saket Kumar                       

Python3

                         # Python Program for Implementing                       
                         # prefix sum array                       
           
                         # Fills prefix sum array                       
                         def                                     fillPrefixSum(arr, n, prefixSum):                       
           
                                                 prefixSum[                                     0                                     ]                                     =                                     arr[                                     0                                     ]                       
           
                                                 # Adding present element                       
                                                 # with previous element                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 prefixSum[i]                                     =                                     prefixSum[i                                     -                                     1                                     ]                                     +                                     arr[i]                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     10                                     ,                                     4                                     ,                                     16                                     ,                                     20                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         prefixSum                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
           
                         fillPrefixSum(arr, n, prefixSum)                       
           
                         for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (prefixSum[i],                                     " "                                     , end                                     =                                     "")                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# Program for Implementing                       
                         // prefix sum arrayclass                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                                 // Fills prefix sum array                       
                                                 static                                     void                                     fillPrefixSum(                                     int                                     [] arr,                                     int                                     n,                       
                                                 int                                     [] prefixSum)                       
                                                 {                       
                                                 prefixSum[0] = arr[0];                       
           
                                                 // Adding present element                       
                                                 // with previous element                       
                                                 for                                     (                                     int                                     i = 1; i < n; ++i)                       
                                                 prefixSum[i] = prefixSum[i - 1] + arr[i];                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 10, 4, 16, 20 };                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     [] prefixSum =                                     new                                     int                                     [n];                       
           
                                                 fillPrefixSum(arr, n, prefixSum);                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(prefixSum[i] +                                     " "                                     );                       
                                                 Console.Write(                                     ""                                     );                       
                                                 }                       
                         }                       
           
                         // This Code is Contributed by nitin mittal                       

PHP

                         <?php                       
                         // PHP program for                       
                         // Implementing prefix                       
                         // sum array                       
           
                         // Fills prefix sum array                       
                         function                                     fillPrefixSum(                                     $arr                                     ,                       
                                                 $n                                     )                       
                         {                       
                                                 $prefixSum                                     =                                     array                                     ();                       
                                                 $prefixSum                                     [0] =                                     $arr                                     [0];                       
           
                                                 // Adding present element                       
                                                 // with previous element                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $prefixSum                                     [                                     $i                                     ] =                                     $prefixSum                                     [                                     $i                                     - 1] +                       
                                                 $arr                                     [                                     $i                                     ];                       
                                   
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $prefixSum                                     [                                     $i                                     ] .                                     " "                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (10, 4, 16, 20);                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
           
                         fillPrefixSum(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // JavaScript Program for Implementing                       
                                                 // prefix sum arrayclass                       
                                   
                                                 // Fills prefix sum array                       
                                                 function                                     fillPrefixSum(arr, n, prefixSum)                       
                                                 {                       
                                                 prefixSum[0] = arr[0];                       
                                   
                                                 // Adding present element                       
                                                 // with previous element                       
                                                 for                                     (let i = 1; i < n; ++i)                       
                                                 prefixSum[i] = prefixSum[i - 1] + arr[i];                       
                                                 }                       
                                   
                                                 let arr = [ 10, 4, 16, 20 ];                       
                                                 let n = arr.length;                       
                                                 let prefixSum =                                     new                                     Array(n);                       
           
                                                 fillPrefixSum(arr, n, prefixSum);                       
           
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 document.write(prefixSum[i] +                                     " "                                     );                       
                                                 document.write(                                     ""                                     );                       
                                   
                         </script>                       

输出：

10 14 30 50

给定一个大小为n的数组arr[]。给定Q个查询，在每个查询中给定L和R，打印从索引L到R的数组元素之和。

C++14

                         #include <iostream>                       
                         using                                     namespace                                     std;                       
                         const                                     int                                     N = 1e5+10;                       
                         int                                     a[N];                       
                         int                                     pf[N];                       
           
                         int                                     main() {                       
                         int                                     n;                       
                         cin >> n;                       
                         for                                     (                                     int                                     i=1; i<=n; i++){                       
                                                 cin >> a[i];                       
                                                 if                                     (i==0)                       
                                                 pf[i]=a[i];                       
                                                 else                       
                                                 pf[i] = pf[i-1] + a[i];                       
                                                 //cout<<pf[i];                       
                         }                       
                         int                                     q;                       
                         cin >> q;                       
                         while                                     (q--){                       
                                                 int                                     l, r;                       
                                                 cin >> l >> r;                       
                         //Calculating sum from l to r.                       
                                                 if                                     (r>n || l<1)                       
                                                 {                       
                                                 cout<<                                     "Please input in range 1 to "                                     <<n<<endl;                       
                                                 break                                     ;                       
                                                 }                       
                                                 if                                     (l==1)                       
                                                 cout << pf[r] << endl;                       
                                                 else                       
                                                 cout << pf[r] - pf[l-1] << endl;                       
                                   
                         }                       
                         return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     6                                     ;                       
                                                 int                                     [] a = {                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     8                                     ,                                     9                                     ,                                     2                                     };                       
                                                 int                                     [] pf =                                     new                                     int                                     [n +                                     2                                     ];                       
                                                 pf[                                     0                                     ] =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 pf[i +                                     1                                     ] = pf[i] + a[i];                       
                                                 }                       
           
                                                 int                                     [][] q                       
                                                 = { {                                     2                                     ,                                     3                                     }, {                                     4                                     ,                                     6                                     }, {                                     1                                     ,                                     5                                     }, {                                     3                                     ,                                     6                                     } };                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < q.length; i++) {                       
                                                 int                                     l = q[i][                                     0                                     ];                       
                                                 int                                     r = q[i][                                     1                                     ];                       
           
                                                 // Calculating sum from r to l.                       
                                                 System.out.print(pf[r] - pf[l -                                     1                                     ] +                                     ""                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code is contributed by umadevi9616                       

Python3

                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     6                                     ;                       
                                                 a                                     =                                     [                                     3                                     ,                                     6                                     ,                                     2                                     ,                                     8                                     ,                                     9                                     ,                                     2                                     ];                       
                                                 pf                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n                                     +                                     2                                     )];                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 pf[i                                     +                                     1                                     ]                                     =                                     pf[i]                                     +                                     a[i];                       
                                   
           
                                                 q                                     =                                     [ [                                     2                                     ,                                     3                                     ],[                                     4                                     ,                                     6                                     ],[                                     1                                     ,                                     5                                     ],[                                     3                                     ,                                     6                                     ]];                       
                                                 for                                     i                                     in                                     range                                     (                                     4                                     ):                       
                                                 l                                     =                                     q[i][                                     0                                     ];                       
                                                 r                                     =                                     q[i][                                     1                                     ];                       
           
                                                 # Calculating sum from r to l.                       
                                                 print                                     (pf[r]                                     -                                     pf[l                                     -                                     1                                     ] );                       
                                   
                         # This code is contributed by gauravrajput1                       

C#

                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 public                                     static                                     void                                     Main(String[] args) {                       
                                                 int                                     n = 6;                       
                                                 int                                     [] a = { 3, 6, 2, 8, 9, 2 };                       
                                                 int                                     [] pf =                                     new                                     int                                     [n + 2];                       
                                                 pf[0] = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 pf[i + 1] = pf[i] + a[i];                       
                                                 }                       
           
                                                 int                                     [,] q = { { 2, 3 }, { 4, 6 }, { 1, 5 }, { 3, 6 } };                       
                                                 for                                     (                                     int                                     i = 0; i < q.GetLength(0); i++) {                       
                                                 int                                     l = q[i,0];                       
                                                 int                                     r = q[i,1];                       
           
                                                 // Calculating sum from r to l.                       
                                                 Console.Write(pf[r] - pf[l - 1] +                                     ""                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code is contributed by gauravrajput1                       

C++14

                         <script>                       
                                   
                                                 var n = 6;                       
                                                 var a = [ 3, 6, 2, 8, 9, 2 ];                       
                                                 var pf = Array(n + 2).fill(0);                       
                                                 pf[0] = 0;                       
                                                 for                                     (i = 0; i < n; i++) {                       
                                                 pf[i + 1] = pf[i] + a[i];                       
                                                 }                       
           
                                                 var q = [ [ 2, 3 ], [ 4, 6 ], [ 1, 5 ], [ 3, 6 ] ];                       
                                                 for                                     (i = 0; i < q.length; i++) {                       
                                                 var l = q[i][0];                       
                                                 var r = q[i][1];                       
           
                                                 // Calculating sum from r to l.                       
                                                 document.write(pf[r-1] - pf[l - 1] +                                     "<br/>"                                     );                       
                                                 }                       
           
                         // This code is contributed by gauravrajput1                       
                         </script>                       

例子：

Input : n = 6       a[ ] = {3, 6, 2, 8, 9, 2}       q = 4       l = 2, r = 3.       l = 4, r = 6.       l = 1, r = 5.       l = 3, r = 6.

Output :  8          19          28          21

时间复杂性： O（n）

应用：

阵列的平衡指数：数组的平衡索引是这样一种索引，即较低索引的元素之和等于较高索引的元素之和。
查找是否有和为0的子数组：给定一个正数和负数的数组，找出是否有一个和为0的子数组（大小至少为1）。
最大子阵列大小，使该大小的所有子阵列的总和小于k：给定一个由n个正整数和一个正整数k组成的数组，任务是找到最大的子数组大小，使该大小的所有子数组的元素之和小于k。
找出可以写成大多数连续素数之和的素数：给定一系列限制。对于每一个极限，求出一个素数，它可以写成小于或等于极限的最连续素数之和。
两个二进制数组中具有相同和的最长跨度：给定两个二进制数组，arr1[]和arr2[]的大小相同n。求最长公共跨度（i，j）的长度，其中j>=i，使得arr1[i]+arr1[i+1]+..+arr1[j]=arr2[i]+arr2[i+1]+arr2[j]。
最大子阵和模m ：给定一个由n个元素和一个整数m组成的数组。任务是找到其子数组模m和的最大值，即找到每个子数组模m的和，并打印此模运算的最大值。
最大子阵列大小，使得该大小的所有子阵列的总和小于k ：给定一个由n个正整数和一个正整数k组成的数组，任务是找到最大子数组大小，使该大小的所有子数组的元素之和小于k。
n个范围内出现的最大整数：给定形式为L和R的n个范围，任务是找到所有范围内出现的最大整数。如果存在多个这样的整数，则打印最小的一个。
购买所有硬币的最低成本，每枚硬币允许额外购买k枚硬币：你会收到一张N种不同面额硬币的清单。你可以支付相当于任何一枚硬币的金额，并可以获得该硬币。此外，一旦您支付了一枚硬币的费用，我们最多可以再选择K枚硬币，并且可以免费获得这些硬币。任务是找到获得给定K值的所有N个硬币所需的最小数量。
任意概率分布方式下的随机数生成器：给定n个数字，每个数字都有一定的出现频率。返回一个概率与其发生频率成正比的随机数。

一个例子问题： 考虑一个大小为n的数组，所有初始值为0。执行从索引“a”到“b”的给定“m”加法操作，并计算数组中的最高元素。添加操作会将100个元素添加到从a到b的所有元素中（包括a和b）。

例子：

Input : n = 5 // We consider array {0, 0, 0, 0, 0}        m = 3.        a = 2, b = 4.        a = 1, b = 3.        a = 1, b = 2.Output : 300Explanation : After I operation -A : 0 100 100 100 0After II operation -A : 100 200 200 100 0After III operation -A : 200 300 200 100 0Highest element : 300

一种简单的方法是运行一个循环’m’次。输入a和b，运行从a到b的循环，将所有元素加100。使用 前缀和数组 :

1 : Run a loop for 'm' times, inputting 'a' and 'b'.2 : Add 100 at index 'a-1' and subtract 100 from index 'b'.3 : After completion of 'm' operations, compute the prefix sum array.4 : Scan the largest element and we're done.

我们所做的是在“a”处添加100，因为这将在使用前缀和数组时向所有元素添加100。从“b+1”中减去100将逆转从“b”开始向元素添加100所做的更改。为了更好地理解：

After I operation -A : 0 100 0 0 -100 Prefix Sum Array : 0 100 100 100 0After II operation -A : 100 100 0 -100 -100Prefix Sum Array : 100 200 200 100 0After III operation -A : 200 100 -100 -100 -100Prefix Sum Array : 200 300 200 100 0Final Prefix Sum Array : 200 300 200 100 0 The required highest element : 300

C++14

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     find(                                     int                                     m, vector<pair<                                     int                                     ,                                     int                                     >> q)                       
                         {                       
                                                 int                                     mx = 0;                       
                                                 vector<                                     int                                     > pre(5,0);                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < m; i++)                       
                                                 {                       
                                                 // take input a and b                       
                                                 int                                     a = q[i].first, b = q[i].second;                       
                                   
                                                 // add 100 at first index and                       
                                                 // subtract 100 from last index                       
                                   
                                                 // pre[1] becomes 100                       
                                                 pre[a-1] += 100;                       
                                   
                                                 // pre[4] becomes -100 and this                       
                                                 pre[b] -=100;                       
                                                 // continues m times as we input diff. values of a and b                       
                                                 }                       
                                                 for                                     (                                     int                                     i = 1; i < 5; i++)                       
                                                 {                       
                                                 // add all values in a cumulative way                       
                                                 pre[i] += pre[i - 1];                       
                                   
                                                 // keep track of max value                       
                                                 mx = max(mx, pre[i]);                       
                                                 }                       
                                   
                                   
                                                 return                                     mx;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                   
                                                 int                                     m = 3;                       
                                                 vector<pair<                                     int                                     ,                                     int                                     >> q = {{2,4},{1,3},{1,2}};                       
                                   
                                   
                                                 // Function call                       
                                                 cout<< find(m,q);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         import                                     java.util.*;                       
           
                         class                                     GFG{                       
                                                 static                                     class                                     pair                       
                                                 {                       
                                                 int                                     first, second;                       
                                                 public                                     pair(                                     int                                     first,                                     int                                     second)                       
                                                 {                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
                                                 }                       
                         static                                     int                                     find(                                     int                                     m, pair []q)                       
                         {                       
                                                 int                                     mx =                                     0                                     ;                       
                                                 int                                     []pre =                                     new                                     int                                     [                                     5                                     ];                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < m; i++)                       
                                                 {                       
                                   
                                                 // take input a and b                       
                                                 int                                     a = q[i].first, b = q[i].second;                       
                                   
                                                 // add 100 at first index and                       
                                                 // subtract 100 from last index                       
                                   
                                                 // pre[1] becomes 100                       
                                                 pre[a-                                     1                                     ] +=                                     100                                     ;                       
                                   
                                                 // pre[4] becomes -100 and this                       
                                                 pre[b] -=                                     100                                     ;                       
                                   
                                                 // continues m times as we input diff. values of a and b                       
                                                 }                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <                                     5                                     ; i++)                       
                                                 {                       
                                   
                                                 // add all values in a cumulative way                       
                                                 pre[i] += pre[i -                                     1                                     ];                       
                                   
                                                 // keep track of max value                       
                                                 mx = Math.max(mx, pre[i]);                       
                                                 }                       
                                   
                                   
                                                 return                                     mx;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                   
                                                 int                                     m =                                     3                                     ;                       
                                                 pair[] q = {                                     new                                     pair(                                     2                                     ,                                     4                                     ),                                     new                                     pair(                                     1                                     ,                                     3                                     ),                                     new                                     pair(                                     1                                     ,                                     2                                     )};                       
                                   
                                   
                                                 // Function call                       
                                                 System.out.print( find(m,q));                       
                         }                       
                         }                       
           
                         // This code is contributed by gauravrajput1                       

Python3

                         # Python implementation of the approach                       
                         def                                     find( m, q):                       
                                                 mx                                     =                                     0                       
                                                 pre                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     5                                     ) ]                       
                                   
                                                 for                                     i                                     in                                     range                                     (m):                       
                                                 # take input a and b                       
                                                 a,b                                     =                                     q[i][                                     0                                     ], q[i][                                     1                                     ]                       
                                   
                                                 # add 100 at first index and                       
                                                 # subtract 100 from last index                       
                                   
                                                 # pre[1] becomes 100                       
                                                 pre[a                                     -                                     1                                     ]                                     +                                     =                                     100                       
                                   
                                                 # pre[4] becomes -100 and this                       
                                                 pre[b]                                     -                                     =                                     100                                     ;                       
                                   
                                                 # continues m times as we input diff. values of a and b                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     5                                     ):                       
                                   
                                                 # add all values in a cumulative way                       
                                                 pre[i]                                     +                                     =                                     pre[i                                     -                                     1                                     ]                       
                                   
                                                 # keep track of max value                       
                                                 mx                                     =                                     max                                     (mx, pre[i])                       
                                                 return                                     mx                       
                                   
                         # Driver Code                       
                         m                                     =                                     3                       
                         q                                     =                                     [[                                     2                                     ,                                     4                                     ],[                                     1                                     ,                                     3                                     ],[                                     1                                     ,                                     2                                     ]]                       
           
                         # Function call                       
                         print                                     (find(m,q))                       
           
                         # This code is contributed by rohitsingh07052                       

C#

                         using                                     System;                       
           
                         public                                     class                                     GFG{                       
                                                 public                                     class                                     pair                       
                                                 {                       
                                                 public                                     int                                     first, second;                       
                                                 public                                     pair(                                     int                                     first,                                     int                                     second)                       
                                                 {                       
                                                 this                                     .first = first;                       
                                                 this                                     .second = second;                       
                                                 }                       
                                                 }                       
                         static                                     int                                     find(                                     int                                     m, pair []q)                       
                         {                       
                                                 int                                     mx = 0;                       
                                                 int                                     []pre =                                     new                                     int                                     [5];                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < m; i++)                       
                                                 {                       
                                   
                                                 // take input a and b                       
                                                 int                                     a = q[i].first, b = q[i].second;                       
                                   
                                                 // add 100 at first index and                       
                                                 // subtract 100 from last index                       
                                   
                                                 // pre[1] becomes 100                       
                                                 pre[a-1] += 100;                       
                                   
                                                 // pre[4] becomes -100 and this                       
                                                 pre[b] -=100;                       
                                   
                                                 // continues m times as we input diff. values of a and b                       
                                                 }                       
                                                 for                                     (                                     int                                     i = 1; i < 5; i++)                       
                                                 {                       
                                   
                                                 // add all values in a cumulative way                       
                                                 pre[i] += pre[i - 1];                       
                                   
                                                 // keep track of max value                       
                                                 mx = Math.Max(mx, pre[i]);                       
                                                 }                       
                                   
                                                 return                                     mx;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     m = 3;                       
                                                 pair[] q = {                                     new                                     pair(2,4),                                     new                                     pair(1,3),                                     new                                     pair(1,2)};                       
                                   
                                   
                                                 // Function call                       
                                                 Console.Write( find(m,q));                       
                         }                       
                         }                       
           
                         // This code is contributed by gauravrajput1.                       

Javascript

                         <script>                       
           
                         function                                     find( m,q)                       
                         {                       
                                                 let mx = 0;                       
                                                 let pre = [0,0,0,0,0];                       
                                   
                                                 for                                     (let i = 0; i < m; i++)                       
                                                 {                       
                                                 // take input a and b                       
                                                 let a = q[i][0], b = q[i][1];                       
                                   
                                                 // add 100 at first index and                       
                                                 // subtract 100 from last index                       
                                   
                                                 // pre[1] becomes 100                       
                                                 pre[a-1] += 100;                       
                                   
                                                 // pre[4] becomes -100 and this                       
                                                 pre[b] -=100;                       
                                                 // continues m times as we input diff. values of a and b                       
                                                 }                       
                                                 for                                     (let i = 1; i < 5; i++)                       
                                                 {                       
                                                 // add all values in a cumulative way                       
                                                 pre[i] += pre[i - 1];                       
                                   
                                                 // keep track of max value                       
                                                 mx = Math.max(mx, pre[i]);                       
                                                 }                       
                                   
                                   
                                                 return                                     mx;                       
                         }                       
           
                         // Driver Code                       
                         let m = 3;                       
                         let q = [[2,4],[1,3],[1,2]];                       
                                   
                                   
                                                 // Function call                       
                                                 document.write(find(m,q));                       
           
                         </script>                       

输出

最近关于前缀和技术的文章 本文由 罗希特·塔普里亚尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章