Fenwick Tree यानि BIT

एक Fenwick tree partial running totals का एक clever set जैसा है जो आपको एक number update करने और किसी भी spot तक total जल्दी ढूंढने देता है।

In this page:

What is Fenwick Tree
Prefix Query
Point Update
Uses
Complexity

Syntax

markup

def update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & -i

def query(i):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & -i
    return total

What is Fenwick Tree

एक Fenwick tree (Binary Indexed Tree) एक compact structure है जो partial, overlapping sums store करती है ताकि यह 'पहले k elements का sum क्या है' queries का जवाब दे सके और individual elements में updates को scratch से recompute करने से कहीं तेज़ handle कर सके।

उदाहरण: What is Fenwick Tree

#include <iostream>
using namespace std;
int main() {
	cout << "BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast");
	}
}

print("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast")

#include <stdio.h>
int main() {
	printf("BIT stores partial overlapping sums to answer prefix-sum queries and handle point updates fast");
	return 0;
}

Prefix Query

किसी index तक एक prefix sum compute करने के लिए, BIT stored blocks की एक छोटी संख्या में पीछे jump करता है — index के binary representation से determined — रास्ते में हर block की value जोड़ते हुए, हर element को एक-एक करके sum करने के बजाय।

उदाहरण: Prefix Query

#include <iostream>
using namespace std;
int bit[9] = {0};
int query(int i) {
	int sum = 0;
	for (; i > 0; i -= i & (-i)) sum += bit[i];
	return sum;
}
int main() {
	bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
	cout << "Prefix sum up to index 4, jumping backward through blocks: " << query(4);
	return 0;
}

public class Main {
	static int[] bit = new int[9];
	static int query(int i) {
		int sum = 0;
		for (; i > 0; i -= i & (-i)) sum += bit[i];
		return sum;
	}
	public static void main(String[] args) {
		bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
		System.out.println("Prefix sum up to index 4, jumping backward through blocks: " + query(4));
	}
}

bit = [0]*9
bit[1], bit[2], bit[3], bit[4] = 2, 6, 5, 18
def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s
print("Prefix sum up to index 4, jumping backward through blocks:", query(4))

#include <stdio.h>
int bit[9] = {0};
int query(int i) {
	int sum = 0;
	for (; i > 0; i -= i & (-i)) sum += bit[i];
	return sum;
}
int main() {
	bit[1]=2; bit[2]=6; bit[3]=5; bit[4]=18;
	printf("Prefix sum up to index 4, jumping backward through blocks: %d", query(4));
	return 0;
}

Point Update

एक single array value update करने के लिए सिर्फ उन मुट्ठी भर stored blocks को adjust करने की ज़रूरत है जिनकी ranges उस index को include करती हैं, queries जैसे ही binary-index logic उपयोग करते हुए structure में आगे jump करके ढूंढा गया लेकिन विपरीत direction में।

उदाहरण: Point Update

#include <iostream>
using namespace std;
int bit[9] = {0};
void update(int i, int delta, int n) {
	for (; i <= n; i += i & (-i)) bit[i] += delta;
}
int main() {
	update(3, 5, 8);
	cout << "Updated index 3 by +5, jumping forward through the same binary-indexed blocks";
	return 0;
}

public class Main {
	static int[] bit = new int[9];
	static void update(int i, int delta, int n) {
		for (; i <= n; i += i & (-i)) bit[i] += delta;
	}
	public static void main(String[] args) {
		update(3, 5, 8);
		System.out.println("Updated index 3 by +5, jumping forward through the same binary-indexed blocks");
	}
}

bit = [0]*9
def update(i, delta, n):
    while i <= n:
        bit[i] += delta
        i += i & (-i)
update(3, 5, 8)
print("Updated index 3 by +5, jumping forward through the same binary-indexed blocks")

#include <stdio.h>
int bit[9] = {0};
void update(int i, int delta, int n) {
	for (; i <= n; i += i & (-i)) bit[i] += delta;
}
int main() {
	update(3, 5, 8);
	printf("Updated index 3 by +5, jumping forward through the same binary-indexed blocks");
	return 0;
}

Uses

Fenwick trees विशेष रूप से handy हैं जब भी एक array बार-बार बदलता है और आपको बार-बार prefix-sum-style answers चाहिए — जैसे running totals track करना, cumulative frequency counts, या competitive programming में 'अब तक कितने elements x से कम हैं'।

उदाहरण: Uses

#include <iostream>
using namespace std;
int main() {
	cout << "Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'");
	}
}

print("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'")

#include <stdio.h>
int main() {
	printf("Running totals, cumulative frequency counts, 'how many elements seen so far are less than x'");
	return 0;
}

Complexity

Update और prefix-query operations दोनों सिर्फ O(log n) blocks छूते हैं, दोनों के लिए logarithmic time देते हुए — हर change के बाद सीधे एक prefix sum recompute करने की O(n) cost से एक बड़ा improvement।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly");
	}
}

print("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly")

#include <stdio.h>
int main() {
	printf("Fenwick tree: O(log n) update and prefix query, vs O(n) recomputing a prefix sum directly");
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Segment Tree Next Lesson → Disjoint Set Union DSU