2D Segment Tree | Range Query | Point Update

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. Topic: 2d Segment Tree

Mr. Pepcoder has a 2D Array, and his Friend love to do operations on thearray. The operations can be a query or an update.

For each query the Friend say four indices x1, y1, x2 and y2, and their father answers back with the sum of the elements of the rectangle whose top left index is x1, y1 and bottom right is x2, y2.

When there is an update, the friend says index (x1,y1) and a value x , and Pepcoder will add x to arr[x1][y1] (so the new value of arr[x1][y1] is arr[x1][y1] + x ).

Because indexing the array from zero is too obscure for friend, all indices start from 1.



Used #DataStructure: #SegmentTree #Array

#TimeComplexity: O(log(n)*log(m))

#SpaceComplexity: O(n*m)

--------------------------------------------------------------

Linked Questions:

1. 2D Segment Tree : https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-interview-prep/segment-tree/2d-segment-tree-official/ojquestion

--------------------------------------------------------------

Smimilar Questions:

1. Max In A Interval - Range Query Point Update : https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-interview-prep/segment-tree/max-in-a-interval-range-query-point-update-official/ojquestion
2. Max In An Interval - Range Query : https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-interview-prep/segment-tree/max-in-an-interval-range-query-official/ojquestion
3. Sum Of Squares : https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-interview-prep/segment-tree/sum-of-squares-official/ojquestion


---------------------------------------------------------------

For detailed information and other exercises, VISIT: www.pepcoding.com

Have a look at our result: https://www.pepcoding.com/placements
Follow us on our FB page: https://www.facebook.com/pepcoding
Follow us on Instagram: https://www.instagram.com/pepcoding
Follow us on LinkedIn: https://www.linkedin.com/company/pepcoding-education


----------------------------------------------------------------

#SegmentTree #RangeQuery #2dSegmentTree

For a better experience and more exercises, VISIT: https://www.pepcoding.com/resources/

Have a look at our result: https://www.pepcoding.com/placements

Follow us on our Youtube page: https://www.youtube.com/c/Pepcoding/featured

Follow us on our FB page: https://www.facebook.com/pepcoding

Follow us on Instagram: https://www.instagram.com/pepcoding

Follow us on LinkedIn: https://www.linkedin.com/company/pepcoding-education

Follow us on Pinterest: https://in.pinterest.com/Pepcoding/_created/

Follow us on Twitter: https://twitter.com/home

.
.
.
Happy Programming !!! Pep it up ??
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer