Dada una array arr[] de tamaño n, su array de suma de prefijos es otra array prefixSum[] del mismo tamaño, tal que el valor de prefixSum[i] es arr[0] + arr[1] + arr[2] … arr[yo].
Ejemplos:
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] << " ";
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for Implementing prefix sum array
#include <stdio.h>
// 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] << " ";
}
// This code is contributed by Aditya Kumar (adityakumar129)
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 Aditya Kumar (adityakumar129)
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>
C++14
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int pf[N];
int main()
{
int n = 6;
int a[] = { 3, 6, 2, 8, 9, 2 };
pf[0] = a[0];
for (int i = 1; i <= n; i++) {
pf[i] = pf[i - 1] + a[i];
// cout<<pf[i];
}
int q = 4;
vector<vector<int> > query
= { { 2, 3 }, { 4, 6 }, { 1, 5 }, { 3, 6 } };
for (int i = 0; i < q; i++) {
int l = query[i][0], r = query[i][1];
if (r > n || l < 1) {
cout << "Please input in range 1 to " << n
<< endl;
continue;
}
if (l == 1)
cout << pf[r-1] << endl;
else
cout << pf[r-1] - pf[l - 2] << 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] + "\n");
}
}
}
// 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] + "\n");
}
}
}
// This code is contributed by gauravrajput1
Javascript
<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>
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>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA