Search
 
SCRIPT & CODE EXAMPLE
 

PYTHON

How to construct a prefix sum array in python?

"""
How to construct a prefix sum array?
Prefix sum array helps respond to sum queries
on an array efficiently.
[1, 3, 4, 8]: original array --> [1, 4, 8, 16]: prefix sum
Sum query sumq(idx1, idx2) = sumq(0, b) - sumq(0, a-1)
Let n denote the size of the original array.
Time complexity: O(n)
Space complexity: O(n)
"""
def prefix_sum(array):
    pref_sum_arr = [0]
    n = len(array)
    for idx in range(1, n+1):
        pref_sum_arr.append(pref_sum_arr[idx-1] + array[idx-1])
    return pref_sum_arr

arr = [1, 3, 4, 8]
print(prefix_sum(arr)[1:])  # [1, 4, 8, 16]
Comment
PREVIOUS NEXT
Code Example
Python :: python keep value recursive function 
Python :: python namespace packages 
Python :: dataframe time index convert tz naive to tz aware 
Python :: extract int from string python 
Python :: strftime 
Python :: iterate over dictionary django 
Python :: convert rgb to a single value 
Python :: how to define function in python 
Python :: takes 1 positional argument but 2 were given python 
Python :: python remove all elemnts in list containing string 
Python :: find percentage of missing values in a column in python 
Python :: python spammer 
Python :: qfiledialog python save 
Python :: python filter dictionary by keys 
Python :: python while loop 
Python :: generate dates between two dates python 
Python :: python plot groupby 
Python :: print multiple lines python 
Python :: dummy variables pandas 
Python :: jinja2 template import html with as 
Python :: read a file with pandas 
Python :: python print trailing zeros 
Python :: python sort array by value 
Python :: python - count total numeber of row in a dataframe 
Python :: how to convert pdf to word using python 
Python :: uninstall python using powershell 
Python :: value_counts with nan 
Python :: python turtle spiral 
Python :: finding odd even python 
Python :: pyspark dataframe to parquet 
ADD CONTENT
Topic
Content
Source link
Name
3+8 =