Cây Chỉ Số Nhị Phân (Binary Indexed Tree) - Codeforces

Trang chủ » Fenwick Tree Là Gì » Cây Chỉ Số Nhị Phân (Binary Indexed Tree) - Codeforces

Có thể bạn quan tâm

Codeforces In English По-русски Enter | Register
  • Home
  • Top
  • Catalog
  • Contests
  • Gym
  • Problemset
  • Groups
  • Rating
  • Edu
  • API
  • Calendar
  • Help
→ Pay attention Contest is runningICPC 2025 Online Winter Challenge powered by Huawei9 daysRegister now » → Streams

2025 ICPC Amritapuri Regional Contest (live commentary)

By aryanc403 Before stream 07:24:09
View all →
→ Top rated
# User Rating
1 Kevin114514 3814
2 Benq 3795
3 jiangly 3722
4 orzdevinwang 3670
5 ecnerwala 3592
6 ksun48 3588
7 tourist 3585
8 VivaciousAubergine 3536
9 Radewoosh 3530
10 dXqwq 3436
Countries | Cities | Organizations View all →
→ Top contributors
# User Contrib.
1 Um_nik 164
2 Qingyu 161
3 adamant 157
4 cry 153
4 Dominater069 153
6 errorgorn 152
7 Proof_by_QED 147
8 TheScrasse 143
9 soullless 142
9 Arpa 142
View all →
→ Find user Handle: → Recent actions
  • joyboyy_ → Codeforces Wrapped 2025 — Your Year in Code Text created or updated
  • Nogaybica → What interesting facts do you know about XOR? New comment(s)
  • awoo → Educational Codeforces Round 186 Editorial New comment(s)
  • khba → How much rating did u get in 2025? New comment(s)
  • mariza_CY → 2026 OIs: Everything we know so far New comment(s)
  • SiyamX7 → Requesting for dark theme in Codeforces Text created or updated
  • Majdaldeen → How to practice using editorials? New comment(s)
  • rimoKR → Any way to filter questions based on A/B/C ? New comment(s)
  • mahriban → 2026 goals Text created or updated
  • Shuvo_06 → Codeforces Access Issue New comment(s)
  • blueslime → Codeforces Notes — A Useful Chrome Extension Text created or updated
  • ismailfateen → ICPC WF 2026 Team List New comment(s)
  • sniper_0101 → Confused in Game Theory Problem New comment(s)
  • Homz → Bitwise Digit DP New comment(s)
  • de_sousa → An Imprecision Problem (Small Imprecision Contest Editorial) New comment(s)
  • KAN → Rounding 2025 New comment(s)
  • twosquares → Good Bye 2025 Editorial New comment(s)
  • Rubikun → What were your favorite problems in 2025? New comment(s)
  • Asakire → Modulo and Integer arithmetic New comment(s)
  • satyam343 → ICPC India Chennai 2025 — 2026 New comment(s)
  • ICPCNews → ICPC 2025 Online Winter Challenge powered by Huawei New comment(s)
  • guest_ducbao_ → dark mode New comment(s)
  • maroonrk → AtCoder Regular Contest 156 Announcement New comment(s) Necropost
  • TheScrasse → Codeforces Round 1066 (Div. 1 + Div. 2) Editorial New comment(s)
  • -firefly- → Codeforces Round 1042 (Div. 3) Editorial New comment(s)
Detailed →
  • gvikei
  • Blog
  • Teams
  • Submissions
  • Contests

gvikei's blog

Cây chỉ số nhị phân (Binary Indexed Tree) By gvikei, 15 years ago, In English (Viết lại từ bài của tác giả paulmcvn chỉ với mục đích cá nhân)Ưu điểm:- Bộ nhớ thấp- Cài đặt đơn giản- Có thể giải được nhiều bài toán về dãy số- Thời gian chạy: O(logN)Khuyết điểm : ==' Khó hỉu vlNội dung chính:Gồm 2 thao tác trên dãy số: A[1..N]SET (index, value) : Tăng phần tử A[index] lên value đơn vịGET (index) : Tính tổng đoạn con A[1..index]Chi tiết:Do các số tự nhiên có thể được biểu diễn dưới dạng tổng các luỹ thừa của 2, ví dụ:VD1: 22= 16 +4 +2= 2^4 + 2^2+ 2 ^1Áp dụng ý tưởng này cho cây nhị phân, ta sẽ biểu diễn tổng A[1..i] dưới dạng các tổng các đoạn con có số phần tử là luỹ thừa của 2.Ý tưởng cài đặt:Gọi S(i,j) là tổng các phần tử của A[i..j] hay S(i,j) = A[i] + A[i+1]... A[j]. Áp dụng với VD1 việc biểu diễn dưới dạng tổng các luỹ thừa của 2 ta được: S(1,22) = S(1,16) + S(17,20) + S(21,22)Để thu được vị trí các đoạn con, ta làm như sau : i - (i AND (-i)). Demo:22 - (22 AND (-22)) = 2020 - (20 AND (-20)) = 16 16 - (16 AND (-16)) = 0Như vậy, cấu trúc cây nhị phân T[] sẽ là: T[i] lưu tổng S((i - i AND (-i)) + 1 , i )(CÒN TIẾP) Tags binary indexed tree
  • Vote: I like it
  • +1
  • Vote: I do not like it
  • Author gvikei
  • Publication date 15 years ago
  • Comments 13
Comments Comments (6) Show archived | Write comment?
OSt 15 years ago, show (+1) #
OSt 15 years ago, hide # | Vote: I like it +3 Vote: I do not like it It's all is interesting, but i can't read it. In what language it was written? → Reply
  • forest 15 years ago, show #
    forest 15 years ago, hide # ^ | Vote: I like it +3 Vote: I do not like it is it how elven looks like ?  → Reply
brklmt 15 years ago, show #
brklmt 15 years ago, hide # | Vote: I like it +3 Vote: I do not like it The language is Vietnamese. In this entry , the author said she copied from another one for her own individual purposes. → Reply
TRUONG 15 years ago, show (+1) #
TRUONG 15 years ago, hide # | Vote: I like it 0 Vote: I do not like it 'Khó hỉu vl', sorry but the team 'vl' not in Vietnamese :)) → Reply
  • lion_it 13 years ago, show #
    lion_it 13 years ago, hide # ^ | Vote: I like it 0 Vote: I do not like it

    and 'hỉu' not in Vietnamese Dictionary

    → Reply
» nhandi 13 years ago, show #
» nhandi 13 years ago, hide # | Vote: I like it 0 Vote: I do not like it

Nói tiếng việt cũng phải nói có văn hóa chứ ._.

→ Reply
In English In Russian ↑ ↓ Codeforces (c) Copyright 2010-2025 Mike Mirzayanov The only programming contests Web 2.0 platform Server time: Jan/02/2026 23:05:51 (g1). Desktop version, switch to mobile version. Privacy Policy | Terms and Conditions Supported by TON ITMO University User lists
Name

Từ khóa » Fenwick Tree Là Gì