Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • 2D prefix sum

    Given a large 2D array of numbers with r rows and c columns, you are asked to calculate the 2D prefix sum of that matrix. 2D prefix sum at a location (r, c) is the sum of all the elements between the corner (0, 0) and the element (r, c). In other words, it’s the sum of elements of the submatrix with corners (0, 0), (r, 0), (r, c), and (0, c).
    Can you calculate the 2D prefix sum for all the locations in the matrix efficiently?
     
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +
    +

    Input

    The first line of the input contains two integers - the number of rows in the matrix r and the number of columns c (1 ≤ r, c ≤ 1000).
    The next r lines contain c integers separated by a space, that represent the elements in the matrix .

    Output

    The program should print r lines containing c numbers representing the 2D prefix sum matrix.

    Examples

    Input
    Output
    3 5 1 2 -3 4 6 -1 3 8 4 0 0 1 -2 0 5
    1 3 0 4 10 0 5 10 18 24 0 6 9 17 28
     

    Constraints

    Time limit: 2 seconds

    Memory limit: 512 MB

    Output limit: 15 MB

    To check your solution you need to sign in
    Sign in to continue