Binary Indexed Tree (Segment Tree & Fenwick Tree)

[MahraibFatima]

Description:

• Used for range queries and updates.
• Segment Tree: Handles range queries like sum, min, or max over a range in O(log n) time.
• Fenwick Tree: Similar to segment trees but simpler, used for cumulative frequency tables.

Checklist:

• [x] Contributor in GSSoC-ext
• [x] Want to work on it

Additional Information:

Segment Tree:

A segment tree is a binary tree used for answering range queries and updates efficiently in O(log n) time. It divides the array into segments and processes range operations like sum, min, or max over intervals. With modifications like lazy propagation, it can handle range updates without recalculating the entire tree.

Fenwick Tree (Binary Indexed Tree):

A Fenwick Tree is a compact data structure used for cumulative frequency tables and range queries. It efficiently supports prefix sum queries and point updates in O(log n) time, using an internal binary representation to propagate changes across nodes. It's simpler and often preferred for smaller use cases like frequency queries.

[github-actions[bot]]

👋 Thank you for raising an issue! We appreciate your effort in helping us improve. Our team will review it shortly. Stay tuned!

[pankaj-bind]

@MahraibFatima assigned