← Back to DSA Course | Chapter 16: Advanced Data Structures | Lesson 3 of 7

Segment Tree क्या है

एक segment tree एक company chart जैसा है जहां हर manager workers की एक range का summary store करता है, इसलिए किसी भी range के बारे में पूछना quick है।

In this page:

  1. What is a Segment Tree
  2. Range Query
  3. Point Update
  4. Common Operations
  5. Complexity
Syntax
markup 
def build(node, start, end):
    if start == end:
        tree[node] = arr[start]
        return
    mid = (start + end) // 2
    build(2 * node, start, mid)
    build(2 * node + 1, mid + 1, end)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

What is a Segment Tree

एक segment tree एक array के ऊपर बनी एक binary tree है जहां हर node array की एक contiguous range के लिए combined information (जैसे sum या minimum) represent करता है, आपको किसी भी subrange के बारे में सवालों का जल्दी जवाब देने देते हुए।

उदाहरण: What is a Segment Tree

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,5,7,8,9};
	cout << "Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,5,7,8,9};
		System.out.println("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range");
	}
}
arr = [2,4,5,7,8,9]
print("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range")
#include <stdio.h>
int main() {
	int arr[] = {2,4,5,7,8,9};
	printf("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range");
	return 0;
}

Range Query

किसी arbitrary range पर एक query का जवाब देने के लिए, tree एक छोटी संख्या में nodes से results combine करता है जो मिलकर बिल्कुल उस range को cover करते हैं, दोनों endpoints के बीच हर individual array element scan करने के बजाय।

उदाहरण: Range Query

#include <iostream>
#include <vector>
using namespace std;
vector<int> tree;
void build(vector<int>& arr, int node, int start, int end) {
	if (start == end) { tree[node] = arr[start]; return; }
	int mid = (start+end)/2;
	build(arr, 2*node, start, mid);
	build(arr, 2*node+1, mid+1, end);
	tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int start, int end, int l, int r) {
	if (r < start || end < l) return 0;
	if (l <= start && end <= r) return tree[node];
	int mid = (start+end)/2;
	return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
int main() {
	vector<int> arr = {2,4,5,7,8,9};
	tree.assign(24, 0);
	build(arr, 1, 0, 5);
	cout << "Sum of range [1,3]: " << query(1, 0, 5, 1, 3);
	return 0;
}
public class Main {
	static int[] tree = new int[24];
	static void build(int[] arr, int node, int start, int end) {
		if (start == end) { tree[node] = arr[start]; return; }
		int mid = (start+end)/2;
		build(arr, 2*node, start, mid);
		build(arr, 2*node+1, mid+1, end);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	static int query(int node, int start, int end, int l, int r) {
		if (r < start || end < l) return 0;
		if (l <= start && end <= r) return tree[node];
		int mid = (start+end)/2;
		return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
	}
	public static void main(String[] args) {
		int[] arr = {2,4,5,7,8,9};
		build(arr, 1, 0, 5);
		System.out.println("Sum of range [1,3]: " + query(1, 0, 5, 1, 3));
	}
}
arr = [2,4,5,7,8,9]
tree = [0]*24
def build(node, start, end):
    if start == end:
        tree[node] = arr[start]
        return
    mid = (start+end)//2
    build(2*node, start, mid)
    build(2*node+1, mid+1, end)
    tree[node] = tree[2*node] + tree[2*node+1]
def query(node, start, end, l, r):
    if r < start or end < l:
        return 0
    if l <= start and end <= r:
        return tree[node]
    mid = (start+end)//2
    return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r)
build(1, 0, 5)
print("Sum of range [1,3]:", query(1, 0, 5, 1, 3))
#include <stdio.h>
int arr[] = {2,4,5,7,8,9};
int tree[24];
void build(int node, int start, int end) {
	if (start == end) { tree[node] = arr[start]; return; }
	int mid = (start+end)/2;
	build(2*node, start, mid);
	build(2*node+1, mid+1, end);
	tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int start, int end, int l, int r) {
	if (r < start || end < l) return 0;
	if (l <= start && end <= r) return tree[node];
	int mid = (start+end)/2;
	return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
int main() {
	build(1, 0, 5);
	printf("Sum of range [1,3]: %d", query(1, 0, 5, 1, 3));
	return 0;
}

Point Update

जब एक single array value बदलती है, सिर्फ उस leaf से root तक path के O(log n) nodes को अपनी stored values recalculate करनी चाहिए, क्योंकि tree का हर दूसरा node उस एक position से unaffected है।

उदाहरण: Point Update

#include <iostream>
using namespace std;
int main() {
	int treeHeight = 3;
	cout << "Only " << treeHeight << " nodes on the leaf-to-root path need recalculating after one value changes";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int treeHeight = 3;
		System.out.println("Only " + treeHeight + " nodes on the leaf-to-root path need recalculating after one value changes");
	}
}
tree_height = 3
print(f"Only {tree_height} nodes on the leaf-to-root path need recalculating after one value changes")
#include <stdio.h>
int main() {
	int treeHeight = 3;
	printf("Only %d nodes on the leaf-to-root path need recalculating after one value changes", treeHeight);
	return 0;
}

Common Operations

Segment trees sums तक सीमित नहीं — वही structure range minimum, range maximum, range GCD, या किसी भी दूसरे operation का जवाब देती है जहां दो adjacent ranges के answers combine करना well-defined हो।

उदाहरण: Common Operations

#include <iostream>
using namespace std;
int main() {
	string ops[] = {"sum", "min", "max", "gcd"};
	for (string o : ops) cout << o << " ";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String[] ops = {"sum", "min", "max", "gcd"};
		for (String o : ops) System.out.print(o + " ");
	}
}
ops = ["sum", "min", "max", "gcd"]
print(*ops)
#include <stdio.h>
int main() {
	char* ops[] = {"sum", "min", "max", "gcd"};
	for (int i = 0; i < 4; i++) printf("%s ", ops[i]);
	return 0;
}

Complexity

Range queries और point updates दोनों O(log n) time में चलते हैं, एक plain array में हर query पर scratch से एक range recompute करने में लगने वाले O(n) से एक major improvement।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch");
	}
}
print("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch")
#include <stdio.h>
int main() {
	printf("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch");
	return 0;
}
Related Topics

Fenwick Tree यानि BIT · Top Tree और Graph समस्याएँ · Minimum Spanning Tree यानि Prim Algorithm · Minimum Spanning Tree यानि Kruskal Algorithm

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Tree array को लगभग 4 * n के बजाय n से size देना, इसलिए nodes overflow करते हैं।
  2. किसी node i के लिए गलत child indexes उपयोग करना (0-based के लिए 2i + 1 और 2i + 2)।
  3. Leaf से root तक सिर्फ path update करने के बजाय एक single change के बाद पूरा tree फिर से बनाना।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Trie Insert and Search Next Lesson → Fenwick Tree BIT

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.