Cumulative (Prefix) Sum (Part 1)

in this article, we will talk about Cumulative sum but first, let me talk about one of the most 

a common problem in computer science if we have an array and we wanna calculate the summation 

of a specific range in this array, you will think of nested loops that sound good. 

but this solution is (o(n)^2) can we get a better solution ??

Yes, we can do that by using (cumulative sum). ok, what is that exactly?

The cumulative sum is a technic we use to get the summation of a specific range in an array in(o(i)).

by generating a new array each element in that array contain the summation of elements before that 

element.

ok, How we can write this code?


ZERO BASED

int range(int s,int e,vector<int>&v){
if(s==0)
    return v[e];
    return v[e]-v[s-1];
}
int main()
{

//zero based
    vector<int>v={1,2,3,4,5,6};
    vector<int>s(v.size(),0);
    for(int i=0;i<v.size();i++){
        s[i]+=(i==0)?v[i]:v[i]+s[i-1];
    }
    cout<<range(2,4,s);
    return 0;
}

ONE BASED

int range(int s,int e,vector<int>&v){
    return v[e]-v[s-1];
}
int main()
{//one based
    vector<int>v={0,1,2,3,4,5,6};
    vector<int>s(v.size(),0);
    for(int i=1;i<v.size();i++){
        s[i]+=v[i]+s[i-1];
    }
    cout<<range(2,4,s);
    return 0;
}


  

    

Comments

Post a Comment

Popular posts from this blog

Leet code (Reverse Integer)

  7.   Reverse Integer Given a signed 32-bit integer  x , return  x  with its digits reversed . If reversing  x  causes the value to go outside the signed 32-bit integer range  [-2 31 , 2 31  - 1] , then return  0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned).   Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: Input: x = 0 Output: 0   Constraints: -2 31  <= x <= 2 31  - 1 Solution class Solution { public:     int reverse(int x) {         int rev = 0;         while (x) {             int pop = x % 10;             x /= 10;             if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;           ...
Read more

Graph Theory(adjacency matrix,adjacency list)

Image
today I will speak about one of the most important topics which are graph theory. I will take a long time in this series because I wanna speak a lot of data structure related to graph theory but in the beginning, I will speak about just two representations which are  (adjacency matrix, adjacency list). adjacency matrix the first let's talk about adjacency matrix .this to make a memory representation for any graph (directed or non-directed) we can imagine that Like  code bool adjacency_matrix[100][100];        Example n=3 0 1 0 1 1 0 0 1 1 for(int i=0;i<n;i++) for(int j=0;j<;j++){ int x; cin>>x; adjacency_matrix[i][j]=x; } adjacency list then I will speak about adjacency list, how to represent it in memory and how we implement it with code code vector< vector<int> > adjList1;               if adjacency list without  weight vector< vector< pair<int, int> ...
Read more

Recursion(Part 1)

In this article I will speak about one of the main topics in computer science and I will write some examples to make you know what is that and how you should use it.   Recursion function it’s a function call itself. And this function is consisting of three parts (Base Case, some Logic,  Sub-problem). 1-Base case: this is a case when it happens this recursion function should stop and gave you the result.     2- some Logic: which happens when function called himself. 3- Sub-problem: in this part, the function calls itself by part of it but this calling should never go to infinity. Ex1: void SayHello(int num) {     if(num < 1)                                                     ...
Read more