Hello! In this article, we will learn about the Segment Tree<\/strong>, which is one of the algorithms that can be useful in coding tests using Java. The segment tree is primarily used to efficiently handle range queries and range updates. In this article, I will explain the basic concept of segment trees, example problems related to it, and the detailed process of solving those problems.<\/p>\n A segment tree is a data structure used to store information about a specific range in an array and to process queries efficiently. It mainly supports the following operations:<\/p>\n A segment tree can process queries in O(log n) time with a space complexity of O(n). This allows for effective handling of large-scale data.<\/p>\n Now, let’s solve a problem using the ‘Segment Tree.’<\/p>\n Given an array of integers, write a program that provides two functions: to find the sum of a specific range and to update the value at a specific index.<\/p>\n The functionalities to be implemented are as follows:<\/p>\n First, we need to implement the segment tree. The segment tree is structured to store the sums from non-leaf nodes down to the leaf nodes. We will declare an array Now, I will write the main program that includes the segment tree class to handle input and process queries.<\/p>\n The time complexity of the segment tree is as follows:<\/p>\nWhat is a Segment Tree?<\/h2>\n
\n
Problem Introduction<\/h2>\n
Problem Description<\/h3>\n
\n
l<\/code> and r<\/code>, return the sum between l<\/code> and r<\/code>.<\/li>\nindex<\/code> to value<\/code>.<\/li>\n<\/ol>\nInput Format<\/h3>\n
\nFirst line: size of the array n (1 \u2264 n \u2264 10^5)\nSecond line: n integers (1 \u2264 arr[i] \u2264 10^9)\nThird line: number of queries q\nNext q lines: the queries are one of two formats:\n 1. 1 l r (range sum query)\n 2. 2 index value (update query)\n<\/pre>\n
Output Format<\/h3>\n
\nOutput the results of the range sum queries line by line.\n<\/pre>\n
Problem Solving Process<\/h2>\n
1. Implementing the Segment Tree<\/h3>\n
tree<\/code> for this purpose and write a method to build the tree.<\/p>\njava\npublic class SegmentTree {\n private int[] tree;\n private int n;\n\n public SegmentTree(int[] arr) {\n n = arr.length;\n tree = new int[n * 4];\n buildTree(arr, 0, 0, n - 1);\n }\n\n private void buildTree(int[] arr, int node, int start, int end) {\n if (start == end) {\n tree[node] = arr[start];\n } else {\n int mid = (start + end) \/ 2;\n buildTree(arr, node * 2 + 1, start, mid);\n buildTree(arr, node * 2 + 2, mid + 1, end);\n tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];\n }\n }\n\n \/\/ Range sum query method\n public int rangeSum(int l, int r) {\n return rangeSumHelper(0, 0, n - 1, l, r);\n }\n\n private int rangeSumHelper(int node, int start, int end, int l, int r) {\n if (r < start || end < l) {\n return 0; \/\/ Query range does not overlap with node range\n }\n if (l <= start && end <= r) {\n return tree[node]; \/\/ Node range is completely within query range\n }\n int mid = (start + end) \/ 2;\n int leftSum = rangeSumHelper(node * 2 + 1, start, mid, l, r);\n int rightSum = rangeSumHelper(node * 2 + 2, mid + 1, end, l, r);\n return leftSum + rightSum;\n }\n\n \/\/ Update method\n public void update(int index, int value) {\n updateHelper(0, 0, n - 1, index, value);\n }\n\n private void updateHelper(int node, int start, int end, int index, int value) {\n if (start == end) {\n tree[node] = value;\n } else {\n int mid = (start + end) \/ 2;\n if (start <= index && index <= mid) {\n updateHelper(node * 2 + 1, start, mid, index, value);\n } else {\n updateHelper(node * 2 + 2, mid + 1, end, index, value);\n }\n tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];\n }\n }\n}\n<\/code><\/pre>\n2. Main Program<\/h3>\n
java\nimport java.util.Scanner;\n\npublic class Main {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n \n int n = scanner.nextInt();\n int[] arr = new int[n];\n \n for (int i = 0; i < n; i++) {\n arr[i] = scanner.nextInt();\n }\n\n SegmentTree segmentTree = new SegmentTree(arr);\n \n int q = scanner.nextInt();\n for (int i = 0; i < q; i++) {\n int type = scanner.nextInt();\n if (type == 1) { \/\/ Range sum query\n int l = scanner.nextInt();\n int r = scanner.nextInt();\n System.out.println(segmentTree.rangeSum(l, r));\n } else if (type == 2) { \/\/ Update query\n int index = scanner.nextInt();\n int value = scanner.nextInt();\n segmentTree.update(index, value);\n }\n }\n \n scanner.close();\n }\n}\n<\/code><\/pre>\n3. Time Complexity Analysis<\/h2>\n