Segment Tree

[hlw-aryan]

The problem is to implement a segment tree data structure for efficient range queries and updates on an array.

I would like to implement a segment tree that supports the following operations:

• Building the segment tree from an input array.
• Querying the sum, minimum, maximum, or any other operation over a given range [l, r] in the array.
• Updating the value of a specific element in the array and propagating the changes through the segment tree.

Solution

• One of the solution is to use a brute-force approach that directly computes the query operation over the given range for each query, resulting in O(n) time complexity for each query. However, this approach is inefficient for repeated queries.
• Another alternative solution is to use a Fenwick tree (or Binary Indexed Tree) for range queries and updates. While Fenwick trees are more space-efficient, they can be limited to specific operations (like sum queries) and may not be as versatile as segment trees.

Additional context Consider handling edge cases such as an empty array or invalid ranges. Discuss the time and space complexity of the segment tree operations and any trade-offs associated with the implementation. It would be helpful to include details about the structure of the segment tree, how the values are stored, and how the queries and updates are performed.

@Kumar-laxmi Please review the proposed implementation and provide feedback or suggestions for improvement.

[Kumar-laxmi]

Assigned! @hlw-aryan : C, C++, Python and Java

[Kumar-laxmi]

@hlw-aryan What is your status on this issue?

[SPARSH1608]

@Kumar-laxmi Can I work on this?

[hlw-aryan]

Around 50% work done.