Segment tree ও Fenwick tree — কোন অংশের উত্তর নিচ্ছি

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

দুই structure-ই array-র কিছু অংশের উত্তর আগে থেকে রাখে। Query-তে দরকারি অংশগুলো নিই; update-এ শুধু বদলানো element-কে ধারণ করা অংশগুলো ঠিক করি। পাশাপাশি পড়ো: Segment tree, Fenwick tree।

Segment tree — ছোট range থেকে বড় range

Array [2,5,1,4,9,3]। প্রতিটি node-এ [বাম index..ডান index] এবং সেই range-এর sum লেখা। এখানে দুই প্রান্তই included।

flowchart TD
  root["[0..5] · sum 24"] --> l["[0..2] · sum 8"]
  root --> r["[3..5] · sum 16"]
  l --> ll["[0..1] · sum 7"]
  l --> v2["[2..2] · 1"]
  r --> rl["[3..4] · sum 13"]
  r --> v5["[5..5] · 3"]
  ll --> v0["[0..0] · 2"]
  ll --> v1["[1..1] · 5"]
  rl --> v3["[3..3] · 4"]
  rl --> v4["[4..4] · 9"]

Leaf একটি array element রাখে। Parent তার দুই child-এর sum রাখে। এই ছয়-element tree-তে 11টি node; সাধারণভাবে এভাবে তৈরি tree-তে 2n−1টি node থাকে, যদিও implementation-এর allocated array বড় হতে পারে।

Query [1,4] — কোন node নেব

চাই 5+1+4+9 = 19। একটি node-এর range পুরো query-র মধ্যে থাকলে তার জমা sum সরাসরি নিই। পুরো বাইরে থাকলে বাদ দিই। আংশিক মিললে children-এ নামি।

flowchart TD
  root["[0..5] · আংশিক, ভাগ করো"] --> l["[0..2] · আংশিক"]
  root --> r["[3..5] · আংশিক"]
  l --> ll["[0..1] · আংশিক"]
  l --> v2["[2..2] · নাও 1"]
  ll --> v0["[0..0] · বাদ"]
  ll --> v1["[1..1] · নাও 5"]
  r --> rl["[3..4] · নাও 13"]
  r --> v5["[5..5] · বাদ"]

নেওয়া range	কোন value ঢুকল	জমা sum
[1,1]	5	5
[2,2]	1	1
[3,4]	4, 9	13
সব মিলিয়ে [1,4]	কোনো gap বা overlap নেই	19

[3,4] পুরোটা নিতে পেরেছি, তাই তার দুই leaf-এ নামিনি। মোট 11টি node-এর মধ্যে 9টিতে গিয়েছি, সরাসরি উত্তর নিয়েছি 3টি থেকে। বড় tree-তে query-র দুই boundary ধরে প্রতি level-এ সীমিত সংখ্যক node ভাঙে; তাই query time O(log n)।

Point update — a[2] = 6

আগে a[2]=1 ছিল। এটি বদলালে কেবল সেই leaf থেকে root পর্যন্ত node-গুলোর sum বদলায়।

ধাপ	Range	পুরোনো মান	নতুন মান
Leaf	[2,2]	1	6
Parent	[0,2]	8	7+6 = 13
Root	[0,5]	24	13+16 = 29

flowchart TD
  root["[0..5] = 29 · বদলেছে"] --> l["[0..2] = 13 · বদলেছে"]
  root --> r["[3..5] = 16"]
  l --> ll["[0..1] = 7"]
  l --> v2["[2..2] = 6 · বদলেছে"]
  r --> rl["[3..4] = 13"]
  r --> v5["[5..5] = 3"]
  ll --> v0["[0..0] = 2"]
  ll --> v1["[1..1] = 5"]
  rl --> v3["[3..3] = 4"]
  rl --> v4["[4..4] = 9"]

এখন একই query(1,4) নেয় [1,1] + [2,2] + [3,4]: উত্তর 5+6+13 = 24।

Fenwick — প্রতিটি index একটি block

এবার index 1 থেকে শুরু। lowbit(i) = i & -i; binary-তে সবচেয়ে ডানের set bit-এর মান। tree[i] রাখে [i−lowbit(i)+1, i] range-এর sum।

n = 16-এর সব block দেখো

i	lowbit(i)	Covered range	Element সংখ্যা
1	1	[1,1]	1
2	2	[1,2]	2
3	1	[3,3]	1
4	4	[1,4]	4
5	1	[5,5]	1
6	2	[5,6]	2
7	1	[7,7]	1
8	8	[1,8]	8
9	1	[9,9]	1
10	2	[9,10]	2
11	1	[11,11]	1
12	4	[9,12]	4
13	1	[13,13]	1
14	2	[13,14]	2
15	1	[15,15]	1
16	16	[1,16]	16

Odd index শুধু নিজের element রাখে। Power-of-two index নিজের আগের পুরো prefix রাখে। বড় index মানেই বড় block নয়: 13-এর block এক element, 12-এর block চার element।

Fenwick query — prefix_sum(13)

বর্তমান tree[i] নিই, তারপর i -= lowbit(i) করি। এতে binary-র সবচেয়ে ডানের set bit মুছে যায়।

flowchart LR
  a["13 · নাও [13..13]"] -->|−1| b["12 · নাও [9..12]"]
  b -->|−4| c["8 · নাও [1..8]"]
  c -->|−8| done["0 · শেষ"]

i	Binary	নেওয়া block	পরের i
13	1101	[13,13]	13−1 = 12
12	1100	[9,12]	12−4 = 8
8	1000	[1,8]	8−8 = 0

এই তিন block যোগ করলে [1,8] + [9,12] + [13,13]—পুরো [1,13], কোনো overlap নেই। 13-এর binary-তে তিনটি set bit, তাই তিনটি block নিয়েছি।

Fenwick update — add(5, +10)

Element 5-কে 10 বাড়ালে সেটিকে ধারণ করা সব block-এর sum 10 বাড়াতে হবে। বর্তমান tree[i] বদলাই, তারপর i += lowbit(i) করি। এখানে n=16।

flowchart LR
  a["5 · [5..5]"] -->|+1| b["6 · [5..6]"]
  b -->|+2| c["8 · [1..8]"]
  c -->|+8| d["16 · [1..16]"]
  d -->|+16| stop["32 > n · শেষ"]

i	Binary	কোন entry বাড়ে	পরের i
5	0101	tree[5] += 10	6
6	0110	tree[6] += 10	8
8	1000	tree[8] += 10	16
16	10000	tree[16] += 10	32; থামি

প্রতিটি visited block-এ index 5 আছে। Update-এর পথ বড় block-এর দিকে যায়; prefix query-র পথ overlap ছাড়া আগের block-এর দিকে যায়। দুটোরই সময় O(log n)।

একই data, আলাদা storage

চার element [2,5,1,4]; এই তুলনায় দুই structure-তেই বাইরের index 1 থেকে ধরছি। Segment tree-এর সব node:

flowchart TD
  all["[1..4] · sum 12"] --> l["[1..2] · sum 7"]
  all --> r["[3..4] · sum 5"]
  l --> a["[1..1] · 2"]
  l --> b["[2..2] · 5"]
  r --> c["[3..3] · 1"]
  r --> d["[4..4] · 4"]

Fenwick storage মাত্র চারটি entry: tree[1]=2, tree[2]=7, tree[3]=1, tree[4]=12। Segment tree-এর মতো প্রতিটি অর্ধের node এখানে নেই; আছে lowbit-নির্ধারিত block।

প্রশ্ন	Segment tree	Fenwick sum tree
[2,4]-এর sum	[2,2] + [3,4] = 5+5	prefix(4)−prefix(1) = 12−2
Element 3-এ +5	Leaf, [3,4], [1,4] বদলায়	tree[3], tree[4] বদলায়
Range min	Combine-এ min ব্যবহার করা যায়	সাধারণ prefix subtraction পদ্ধতি চলে না

নিজে করো: update-এর পরে এই দুই structure দিয়ে আবার [2,4]-এর sum বের করো। দুই উত্তরই 15 হওয়া উচিত।