In the world of competitive programming and advanced data structures, the Binary Indexed Tree (BIT), also known as a Fenwick Tree, stands out as a powerful and efficient tool. This data structure, invented by Peter M. Fenwick in 1994, offers a clever way to perform range queries and updates on an array in logarithmic time. In this comprehensive guide, we’ll dive deep into the Binary Indexed Tree, exploring its concepts, implementation, and applications.<\/p>\n
Table of Contents<\/h2>\n\n- Introduction to Binary Indexed Trees<\/a><\/li>\n
- The Concept Behind Binary Indexed Trees<\/a><\/li>\n
- Basic Operations<\/a><\/li>\n
- Implementation in Python<\/a><\/li>\n
- Time Complexity Analysis<\/a><\/li>\n
- Applications and Use Cases<\/a><\/li>\n
- Comparison with Other Data Structures<\/a><\/li>\n
- Advanced Techniques and Variations<\/a><\/li>\n
- Practice Problems<\/a><\/li>\n
- Conclusion<\/a><\/li>\n<\/ol>\n
1. Introduction to Binary Indexed Trees<\/h2>\n
A Binary Indexed Tree, or Fenwick Tree, is a data structure that provides efficient methods for calculating and manipulating cumulative frequency tables. It was designed to improve the performance of prefix sum calculations and range sum queries in arrays.<\/p>\n
The main advantages of Binary Indexed Trees include:<\/p>\n
\n- Efficient updates and queries in O(log n) time complexity<\/li>\n
- Simple implementation compared to other advanced data structures<\/li>\n
- Space-efficient, requiring only O(n) space<\/li>\n
- Versatility in solving various problems involving range queries<\/li>\n<\/ul>\n
2. The Concept Behind Binary Indexed Trees<\/h2>\n
The key idea behind a Binary Indexed Tree is to represent an array of numbers in a way that allows quick cumulative frequency computations. It achieves this by storing partial sum information in an intelligent manner.<\/p>\n
To understand how a BIT works, let’s break down its core concepts:<\/p>\n
2.1 Binary Representation<\/h3>\n
The structure of a BIT is closely tied to the binary representation of indices. Each index in the BIT represents a range of elements in the original array. The size of this range is determined by the least significant bit (LSB) of the index.<\/p>\n
2.2 Parent-Child Relationship<\/h3>\n
In a BIT, each element is responsible for a certain range of the original array. The parent of an element is responsible for a larger range that includes the range of its child. This hierarchical structure allows for efficient querying and updating.<\/p>\n
2.3 Prefix Sums<\/h3>\n
The BIT stores partial sums in such a way that the sum of any prefix of the array can be computed by combining a small number of these partial sums. This is the key to its efficiency in range sum queries.<\/p>\n
3. Basic Operations<\/h2>\n
The two fundamental operations in a Binary Indexed Tree are:<\/p>\n
3.1 Update Operation<\/h3>\n
The update operation is used to modify a single element in the array. When an element is updated, all the partial sums that include this element need to be updated as well. This is done efficiently by updating only the necessary nodes in the tree.<\/p>\n
3.2 Query Operation<\/h3>\n
The query operation is used to compute the sum of elements in a given range. It does this by combining the partial sums stored in the BIT nodes.<\/p>\n
4. Implementation in Python<\/h2>\n
Let’s implement a Binary Indexed Tree in Python. We’ll create a class that supports both update and query operations.<\/p>\n
class BinaryIndexedTree:\n def __init__(self, size):\n self.size = size\n self.tree = [0] * (size + 1)\n\n def update(self, index, value):\n while index <= self.size:\n self.tree[index] += value\n index += index & (-index)\n\n def query(self, index):\n total = 0\n while index > 0:\n total += self.tree[index]\n index -= index & (-index)\n return total\n\n def range_query(self, left, right):\n return self.query(right) - self.query(left - 1)\n<\/code><\/pre>\nLet’s break down the implementation:<\/p>\n
\n- The
__init__<\/code> method initializes the BIT with a given size. Note that we allocate an extra element (size + 1) because BITs are typically 1-indexed.<\/li>\n- The
update<\/code> method adds a value to an element and updates all necessary partial sums.<\/li>\n- The
query<\/code> method computes the sum of elements from index 1 to the given index.<\/li>\n- The
range_query<\/code> method computes the sum of elements in a given range by using the difference of two prefix sums.<\/li>\n<\/ul>\nNow, let’s see how to use this implementation:<\/p>\n
# Create a BIT for an array of size 10\nbit = BinaryIndexedTree(10)\n\n# Update some values\nbit.update(1, 3)\nbit.update(2, 2)\nbit.update(3, 5)\nbit.update(4, 1)\nbit.update(5, 4)\n\n# Query prefix sums\nprint(bit.query(3)) # Sum of elements from 1 to 3: 3 + 2 + 5 = 10\nprint(bit.query(5)) # Sum of elements from 1 to 5: 3 + 2 + 5 + 1 + 4 = 15\n\n# Query range sum\nprint(bit.range_query(2, 4)) # Sum of elements from 2 to 4: 2 + 5 + 1 = 8\n<\/code><\/pre>\n5. Time Complexity Analysis<\/h2>\n
The efficiency of Binary Indexed Trees comes from their clever use of binary representation. Let’s analyze the time complexity of the main operations:<\/p>\n
5.1 Update Operation<\/h3>\n
The update operation has a time complexity of O(log n), where n is the size of the array. This is because in each step, we move to a parent node by adding the least significant bit, which effectively divides the remaining distance by 2.<\/p>\n
5.2 Query Operation<\/h3>\n
The query operation also has a time complexity of O(log n). Similar to the update operation, we move up the tree by removing the least significant bit in each step, which again divides the remaining distance by 2.<\/p>\n
5.3 Range Query<\/h3>\n
The range query operation involves two query operations, so its time complexity is also O(log n).<\/p>\n
5.4 Space Complexity<\/h3>\n
The space complexity of a Binary Indexed Tree is O(n), as it requires an array of size n+1 to store the partial sums.<\/p>\n
6. Applications and Use Cases<\/h2>\n
Binary Indexed Trees are versatile data structures with numerous applications in competitive programming and real-world scenarios. Some common use cases include:<\/p>\n
6.1 Range Sum Queries<\/h3>\n
BITs excel at answering range sum queries efficiently, making them ideal for problems involving cumulative frequencies or sums over ranges.<\/p>\n
6.2 Data Analysis<\/h3>\n
In data analysis and statistics, BITs can be used to efficiently compute moving averages or maintain cumulative statistics over dynamic datasets.<\/p>\n
6.3 Computational Geometry<\/h3>\n
BITs can be applied to solve various computational geometry problems, such as counting inversions or finding the number of smaller elements to the right.<\/p>\n
6.4 Game Development<\/h3>\n
In game development, BITs can be used for efficient collision detection or managing game state that requires frequent updates and range queries.<\/p>\n
7. Comparison with Other Data Structures<\/h2>\n
To better understand the strengths of Binary Indexed Trees, let’s compare them with other data structures used for similar purposes:<\/p>\n
7.1 BIT vs. Segment Tree<\/h3>\n
Both BITs and Segment Trees support range queries and updates in O(log n) time. However:<\/p>\n
\n- BITs are simpler to implement and have a smaller constant factor in their time complexity.<\/li>\n
- Segment Trees are more versatile and can handle a wider range of operations (like finding the minimum in a range).<\/li>\n
- BITs use less memory (O(n) vs O(n log n) for Segment Trees).<\/li>\n<\/ul>\n
7.2 BIT vs. Prefix Sum Array<\/h3>\n
Prefix Sum Arrays offer O(1) range sum queries but O(n) updates. BITs provide a balance with O(log n) for both operations, making them more suitable for scenarios with frequent updates.<\/p>\n
7.3 BIT vs. Square Root Decomposition<\/h3>\n
Square Root Decomposition offers O(√n) complexity for both updates and queries. BITs are generally faster for larger datasets but may be overkill for smaller arrays where Square Root Decomposition could be simpler and effective.<\/p>\n
8. Advanced Techniques and Variations<\/h2>\n
While the basic Binary Indexed Tree is powerful, there are several advanced techniques and variations that extend its capabilities:<\/p>\n
8.1 2D Binary Indexed Tree<\/h3>\n
A 2D BIT can handle range sum queries and updates on a 2D grid. It’s particularly useful in problems involving matrices or 2D coordinate systems.<\/p>\n
class BinaryIndexedTree2D:\n def __init__(self, rows, cols):\n self.rows = rows\n self.cols = cols\n self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]\n\n def update(self, row, col, value):\n i = row\n while i <= self.rows:\n j = col\n while j <= self.cols:\n self.tree[i][j] += value\n j += j & (-j)\n i += i & (-i)\n\n def query(self, row, col):\n total = 0\n i = row\n while i > 0:\n j = col\n while j > 0:\n total += self.tree[i][j]\n j -= j & (-j)\n i -= i & (-i)\n return total\n\n def range_query(self, row1, col1, row2, col2):\n return (self.query(row2, col2) - self.query(row1 - 1, col2) -\n self.query(row2, col1 - 1) + self.query(row1 - 1, col1 - 1))\n<\/code><\/pre>\n8.2 Range Update, Point Query<\/h3>\n
While the standard BIT supports point updates and range queries, it’s possible to modify it to support range updates and point queries. This is achieved by storing differences between consecutive elements instead of the actual values.<\/p>\n
8.3 Order Statistic Tree<\/h3>\n
By using a BIT to count the number of elements, we can implement an Order Statistic Tree, which can find the k-th smallest element in a dynamic set efficiently.<\/p>\n
8.4 Persistent Binary Indexed Tree<\/h3>\n
A persistent version of BIT allows querying previous versions of the data structure after each update, which can be useful in certain algorithmic problems.<\/p>\n
9. Practice Problems<\/h2>\n
To solidify your understanding of Binary Indexed Trees, here are some practice problems from various online judges:<\/p>\n
\n- SPOJ – Inversion Count<\/a>: A classic problem that can be efficiently solved using a BIT.<\/li>\n
- Codeforces – Multiset<\/a>: This problem requires a creative use of BIT for both insertion and deletion operations.<\/li>\n
- LeetCode – Range Sum Query – Mutable<\/a>: A straightforward application of BIT for range sum queries with updates.<\/li>\n
- HackerEarth – Help Ashu<\/a>: This problem combines BIT with parity checking.<\/li>\n
- CodeChef – Spread the Word<\/a>: A challenging problem that requires a 2D BIT implementation.<\/li>\n<\/ol>\n
Working through these problems will help you gain practical experience in implementing and applying Binary Indexed Trees to solve various algorithmic challenges.<\/p>\n
10. Conclusion<\/h2>\n
Binary Indexed Trees are a powerful and elegant data structure that provide an efficient solution for range query problems. Their simplicity in implementation, coupled with their logarithmic time complexity for both updates and queries, makes them an invaluable tool in a programmer’s arsenal.<\/p>\n
As you continue your journey in algorithmic problem-solving and competitive programming, mastering the Binary Indexed Tree will undoubtedly enhance your ability to tackle a wide range of problems efficiently. Remember that practice is key to fully grasping the nuances of this data structure and its applications.<\/p>\n
Whether you’re preparing for technical interviews, participating in programming contests, or working on real-world applications that require efficient range queries, the knowledge of Binary Indexed Trees will serve you well. Keep exploring, practicing, and pushing the boundaries of what you can achieve with this remarkable data structure!<\/p>\n<\/article>\n
<\/body><\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
In the world of competitive programming and advanced data structures, the Binary Indexed Tree (BIT), also known as a Fenwick…<\/p>\n","protected":false},"author":1,"featured_media":4610,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4611","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4611"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4611"}],"version-history":[{"count":0,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4611\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4610"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
1. Introduction to Binary Indexed Trees<\/h2>\n
A Binary Indexed Tree, or Fenwick Tree, is a data structure that provides efficient methods for calculating and manipulating cumulative frequency tables. It was designed to improve the performance of prefix sum calculations and range sum queries in arrays.<\/p>\n
The main advantages of Binary Indexed Trees include:<\/p>\n
- \n
- Efficient updates and queries in O(log n) time complexity<\/li>\n
- Simple implementation compared to other advanced data structures<\/li>\n
- Space-efficient, requiring only O(n) space<\/li>\n
- Versatility in solving various problems involving range queries<\/li>\n<\/ul>\n
2. The Concept Behind Binary Indexed Trees<\/h2>\n
The key idea behind a Binary Indexed Tree is to represent an array of numbers in a way that allows quick cumulative frequency computations. It achieves this by storing partial sum information in an intelligent manner.<\/p>\n
To understand how a BIT works, let’s break down its core concepts:<\/p>\n
2.1 Binary Representation<\/h3>\n
The structure of a BIT is closely tied to the binary representation of indices. Each index in the BIT represents a range of elements in the original array. The size of this range is determined by the least significant bit (LSB) of the index.<\/p>\n
2.2 Parent-Child Relationship<\/h3>\n
In a BIT, each element is responsible for a certain range of the original array. The parent of an element is responsible for a larger range that includes the range of its child. This hierarchical structure allows for efficient querying and updating.<\/p>\n
2.3 Prefix Sums<\/h3>\n
The BIT stores partial sums in such a way that the sum of any prefix of the array can be computed by combining a small number of these partial sums. This is the key to its efficiency in range sum queries.<\/p>\n
3. Basic Operations<\/h2>\n
The two fundamental operations in a Binary Indexed Tree are:<\/p>\n
3.1 Update Operation<\/h3>\n
The update operation is used to modify a single element in the array. When an element is updated, all the partial sums that include this element need to be updated as well. This is done efficiently by updating only the necessary nodes in the tree.<\/p>\n
3.2 Query Operation<\/h3>\n
The query operation is used to compute the sum of elements in a given range. It does this by combining the partial sums stored in the BIT nodes.<\/p>\n
4. Implementation in Python<\/h2>\n
Let’s implement a Binary Indexed Tree in Python. We’ll create a class that supports both update and query operations.<\/p>\n
class BinaryIndexedTree:\n def __init__(self, size):\n self.size = size\n self.tree = [0] * (size + 1)\n\n def update(self, index, value):\n while index <= self.size:\n self.tree[index] += value\n index += index & (-index)\n\n def query(self, index):\n total = 0\n while index > 0:\n total += self.tree[index]\n index -= index & (-index)\n return total\n\n def range_query(self, left, right):\n return self.query(right) - self.query(left - 1)\n<\/code><\/pre>\nLet’s break down the implementation:<\/p>\n
- \n
- The
__init__<\/code> method initializes the BIT with a given size. Note that we allocate an extra element (size + 1) because BITs are typically 1-indexed.<\/li>\n- The
update<\/code> method adds a value to an element and updates all necessary partial sums.<\/li>\n- The
query<\/code> method computes the sum of elements from index 1 to the given index.<\/li>\n- The
range_query<\/code> method computes the sum of elements in a given range by using the difference of two prefix sums.<\/li>\n<\/ul>\nNow, let’s see how to use this implementation:<\/p>\n
# Create a BIT for an array of size 10\nbit = BinaryIndexedTree(10)\n\n# Update some values\nbit.update(1, 3)\nbit.update(2, 2)\nbit.update(3, 5)\nbit.update(4, 1)\nbit.update(5, 4)\n\n# Query prefix sums\nprint(bit.query(3)) # Sum of elements from 1 to 3: 3 + 2 + 5 = 10\nprint(bit.query(5)) # Sum of elements from 1 to 5: 3 + 2 + 5 + 1 + 4 = 15\n\n# Query range sum\nprint(bit.range_query(2, 4)) # Sum of elements from 2 to 4: 2 + 5 + 1 = 8\n<\/code><\/pre>\n5. Time Complexity Analysis<\/h2>\n
The efficiency of Binary Indexed Trees comes from their clever use of binary representation. Let’s analyze the time complexity of the main operations:<\/p>\n
5.1 Update Operation<\/h3>\n
The update operation has a time complexity of O(log n), where n is the size of the array. This is because in each step, we move to a parent node by adding the least significant bit, which effectively divides the remaining distance by 2.<\/p>\n
5.2 Query Operation<\/h3>\n
The query operation also has a time complexity of O(log n). Similar to the update operation, we move up the tree by removing the least significant bit in each step, which again divides the remaining distance by 2.<\/p>\n
5.3 Range Query<\/h3>\n
The range query operation involves two query operations, so its time complexity is also O(log n).<\/p>\n
5.4 Space Complexity<\/h3>\n
The space complexity of a Binary Indexed Tree is O(n), as it requires an array of size n+1 to store the partial sums.<\/p>\n
6. Applications and Use Cases<\/h2>\n
Binary Indexed Trees are versatile data structures with numerous applications in competitive programming and real-world scenarios. Some common use cases include:<\/p>\n
6.1 Range Sum Queries<\/h3>\n
BITs excel at answering range sum queries efficiently, making them ideal for problems involving cumulative frequencies or sums over ranges.<\/p>\n
6.2 Data Analysis<\/h3>\n
In data analysis and statistics, BITs can be used to efficiently compute moving averages or maintain cumulative statistics over dynamic datasets.<\/p>\n
6.3 Computational Geometry<\/h3>\n
BITs can be applied to solve various computational geometry problems, such as counting inversions or finding the number of smaller elements to the right.<\/p>\n
6.4 Game Development<\/h3>\n
In game development, BITs can be used for efficient collision detection or managing game state that requires frequent updates and range queries.<\/p>\n
7. Comparison with Other Data Structures<\/h2>\n
To better understand the strengths of Binary Indexed Trees, let’s compare them with other data structures used for similar purposes:<\/p>\n
7.1 BIT vs. Segment Tree<\/h3>\n
Both BITs and Segment Trees support range queries and updates in O(log n) time. However:<\/p>\n
- \n
- BITs are simpler to implement and have a smaller constant factor in their time complexity.<\/li>\n
- Segment Trees are more versatile and can handle a wider range of operations (like finding the minimum in a range).<\/li>\n
- BITs use less memory (O(n) vs O(n log n) for Segment Trees).<\/li>\n<\/ul>\n
7.2 BIT vs. Prefix Sum Array<\/h3>\n
Prefix Sum Arrays offer O(1) range sum queries but O(n) updates. BITs provide a balance with O(log n) for both operations, making them more suitable for scenarios with frequent updates.<\/p>\n
7.3 BIT vs. Square Root Decomposition<\/h3>\n
Square Root Decomposition offers O(√n) complexity for both updates and queries. BITs are generally faster for larger datasets but may be overkill for smaller arrays where Square Root Decomposition could be simpler and effective.<\/p>\n
8. Advanced Techniques and Variations<\/h2>\n
While the basic Binary Indexed Tree is powerful, there are several advanced techniques and variations that extend its capabilities:<\/p>\n
8.1 2D Binary Indexed Tree<\/h3>\n
A 2D BIT can handle range sum queries and updates on a 2D grid. It’s particularly useful in problems involving matrices or 2D coordinate systems.<\/p>\n
class BinaryIndexedTree2D:\n def __init__(self, rows, cols):\n self.rows = rows\n self.cols = cols\n self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]\n\n def update(self, row, col, value):\n i = row\n while i <= self.rows:\n j = col\n while j <= self.cols:\n self.tree[i][j] += value\n j += j & (-j)\n i += i & (-i)\n\n def query(self, row, col):\n total = 0\n i = row\n while i > 0:\n j = col\n while j > 0:\n total += self.tree[i][j]\n j -= j & (-j)\n i -= i & (-i)\n return total\n\n def range_query(self, row1, col1, row2, col2):\n return (self.query(row2, col2) - self.query(row1 - 1, col2) -\n self.query(row2, col1 - 1) + self.query(row1 - 1, col1 - 1))\n<\/code><\/pre>\n8.2 Range Update, Point Query<\/h3>\n
While the standard BIT supports point updates and range queries, it’s possible to modify it to support range updates and point queries. This is achieved by storing differences between consecutive elements instead of the actual values.<\/p>\n
8.3 Order Statistic Tree<\/h3>\n
By using a BIT to count the number of elements, we can implement an Order Statistic Tree, which can find the k-th smallest element in a dynamic set efficiently.<\/p>\n
8.4 Persistent Binary Indexed Tree<\/h3>\n
A persistent version of BIT allows querying previous versions of the data structure after each update, which can be useful in certain algorithmic problems.<\/p>\n
9. Practice Problems<\/h2>\n
To solidify your understanding of Binary Indexed Trees, here are some practice problems from various online judges:<\/p>\n
- \n
- SPOJ – Inversion Count<\/a>: A classic problem that can be efficiently solved using a BIT.<\/li>\n
- Codeforces – Multiset<\/a>: This problem requires a creative use of BIT for both insertion and deletion operations.<\/li>\n
- LeetCode – Range Sum Query – Mutable<\/a>: A straightforward application of BIT for range sum queries with updates.<\/li>\n
- HackerEarth – Help Ashu<\/a>: This problem combines BIT with parity checking.<\/li>\n
- CodeChef – Spread the Word<\/a>: A challenging problem that requires a 2D BIT implementation.<\/li>\n<\/ol>\n
Working through these problems will help you gain practical experience in implementing and applying Binary Indexed Trees to solve various algorithmic challenges.<\/p>\n
10. Conclusion<\/h2>\n
Binary Indexed Trees are a powerful and elegant data structure that provide an efficient solution for range query problems. Their simplicity in implementation, coupled with their logarithmic time complexity for both updates and queries, makes them an invaluable tool in a programmer’s arsenal.<\/p>\n
As you continue your journey in algorithmic problem-solving and competitive programming, mastering the Binary Indexed Tree will undoubtedly enhance your ability to tackle a wide range of problems efficiently. Remember that practice is key to fully grasping the nuances of this data structure and its applications.<\/p>\n
Whether you’re preparing for technical interviews, participating in programming contests, or working on real-world applications that require efficient range queries, the knowledge of Binary Indexed Trees will serve you well. Keep exploring, practicing, and pushing the boundaries of what you can achieve with this remarkable data structure!<\/p>\n<\/article>\n
<\/body><\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
In the world of competitive programming and advanced data structures, the Binary Indexed Tree (BIT), also known as a Fenwick…<\/p>\n","protected":false},"author":1,"featured_media":4610,"comment_status":"","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4611","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4611"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4611"}],"version-history":[{"count":0,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4611\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4610"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Codeforces – Multiset<\/a>: This problem requires a creative use of BIT for both insertion and deletion operations.<\/li>\n
- SPOJ – Inversion Count<\/a>: A classic problem that can be efficiently solved using a BIT.<\/li>\n
- The
- The