Segment Tree Implementation for Range Queries and Updates
The segment tree is constructed recursively. Each node tracks its segment boundaries [left, right]. Leaf nodes correspond to individual array elements, while enternal nodes store the sum of their children.
struct SegmentTree {
int left[MAX_N * 4], right[MAX_N * 4];
long long value[MAX_N * 4], lazy[MAX_N * 4];
void build(int l, int ...
Posted on Thu, 18 Jun 2026 17:26:51 +0000 by hkothari
Fenwick Tree Mastery: Core Operations and Practical Applications
Core Functinos
1. Point Update Operation
void update(int idx, int delta) {
while (idx <= arrSize) {
tree[idx] += delta;
idx += idx & -idx; // Propagate to parent nodes
}
}
2. Prefix Sum Query
long long query(int pos) {
long long result = 0;
while (pos > 0) {
result += tree[pos];
pos -= pos & -pos; // Move ...
Posted on Sat, 13 Jun 2026 18:23:20 +0000 by rupam_jaiswal
Introduction to Persistent Segment Trees
A common question arises: what distinguishes a Chairman Tree from a Persistent Segment Tree? The answer lies in their definitions—a Chairman Tree is specifically a persistent weighted segment tree, which is a specialized application of the persistent segment tree structure.
Definition
A persistent segment tree is a data structure that preserves ...
Posted on Fri, 15 May 2026 12:19:01 +0000 by Ind007