Hello! In this lecture, we will take a closer look at the segment tree, which is one of the data structures. The segment tree is a powerful data structure that can efficiently handle interval queries, especially useful for calculating the range sum, range minimum, and range maximum of an array. In this text, we will explore the basic concepts of segment trees, how to implement them, and solve problems that are frequently asked in practice.<\/p>\n
A segment tree is a powerful tool for efficiently managing the interval information of an array. Typically, when the size of the array is N, a segment tree uses approximately 2 * 2\u2308log\u2082(N)\u2309<\/sup> memory space. This is due to the use of a complete binary tree structure. Fundamentally, the segment tree can perform the following two operations efficiently:<\/p>\n The segment tree is made up of nodes, each representing a specific interval. For example, there is a root node that manages the interval from index 0 to N-1 of the array, and this node divides the array into two halves through two child nodes. By continuously dividing the array in this manner, each node holds the information of a specific interval.<\/p>\n Each node contains the following information:<\/p>\n To implement a segment tree, we first need to build the tree. For this, we use a method that recursively creates segment tree nodes based on the input array. As a simple example, let’s create a segment tree for range sums.<\/p>\n The segment tree now needs to add a feature to calculate range sums. To handle range sum queries, we will add the following function:<\/p>\n We will also add a function to update the elements of the array. When changing a specific index of the array, here\u2019s how we can quickly update the information in the segment tree:<\/p>\n Now that we have looked at the basic structure of the segment tree and how to perform queries and updates, let's tackle a problem that is frequently asked in practice. The problem is as follows:<\/p>\n Given an array, answer the following questions:<\/p>\n\n
2. Structure of the Segment Tree<\/h2>\n
2.1 Node Definition<\/h3>\n
\n
3. Creating and Querying the Segment Tree<\/h2>\n
\n
\n\/\/ Swift Code\nclass SegmentTree {\n var tree: [Int] \/\/ Array to store the segment tree\n var n: Int \/\/ Size of the array\n\n init(_ data: [Int]) {\n self.n = data.count\n self.tree = Array(repeating: 0, count: 4 * n) \/\/ Initialize the tree array\n buildTree(data: data, node: 1, start: 0, end: n - 1)\n }\n\n \/\/ Build the segment tree using the interval of the array\n func buildTree(data: [Int], node: Int, start: Int, end: Int) {\n if start == end {\n tree[node] = data[start] \/\/ Store value in leaf node\n } else {\n let mid = (start + end) \/ 2\n buildTree(data: data, node: 2 * node, start: start, end: mid) \/\/ Left subtree\n buildTree(data: data, node: 2 * node + 1, start: mid + 1, end: end) \/\/ Right subtree\n tree[node] = tree[2 * node] + tree[2 * node + 1] \/\/ Update parent node value\n }\n }\n}\n<\/code>\n<\/pre>\n4. Processing Segment Tree Queries<\/h2>\n
\n
\n\/\/ Function to calculate the sum of a given interval\nfunc query(node: Int, start: Int, end: Int, l: Int, r: Int) -> Int {\n if r < start || end < l { \/\/ If intervals do not overlap\n return 0 \/\/ Default value\n }\n if l <= start && end <= r { \/\/ If the interval is completely contained\n return tree[node]\n }\n let mid = (start + end) \/ 2\n let leftSum = query(node: 2 * node, start: start, end: mid, l: l, r: r) \/\/ Query left subtree\n let rightSum = query(node: 2 * node + 1, start: mid + 1, end: end, l: l, r: r) \/\/ Query right subtree\n return leftSum + rightSum \/\/ Sum the results\n}\n<\/code>\n<\/pre>\n5. Updating the Segment Tree<\/h2>\n
\n
\n\/\/ Function to update a specific index of the array\nfunc update(node: Int, start: Int, end: Int, idx: Int, value: Int) {\n if start == end { \/\/ Reached leaf node\n tree[node] = value \/\/ Update the node\n } else {\n let mid = (start + end) \/ 2\n if start <= idx && idx <= mid {\n update(node: 2 * node, start: start, end: mid, idx: idx, value: value) \/\/ Update left subtree\n } else {\n update(node: 2 * node + 1, start: mid + 1, end: end, idx: idx, value: value) \/\/ Update right subtree\n }\n tree[node] = tree[2 * node] + tree[2 * node + 1] \/\/ Update parent node value\n }\n}\n<\/code>\n<\/pre>\n6. Example of a Practical Problem<\/h2>\n
Problem Description<\/h3>\n
\n
Input Format<\/h3>\n
\nN (array size)\narr[0], arr[1], ..., arr[N-1]\nQ (number of queries)\nEach query is given in the following format:\n1 L R (range sum query)\n2 I V (update query)\n<\/pre>\n
Output Format<\/h3>\n
\nOutput for each range sum query\n<\/pre>\n
Example<\/h3>\n
\n5\n1 2 3 4 5\n3\n1 1 3\n2 2 10\n1 1 3\n<\/pre>\n
\nExample Output\n6\n<\/pre>\n
7. Problem-Solving Process<\/h2>\n