\n One of the techniques for efficiently solving problems in algorithm competitions or coding interviews is the Segment Tree<\/strong>. \n A segment tree is a data structure used to efficiently manage information about intervals of an array. \n The segment tree consists of the following structure:\n<\/p>\n \n Now, let’s introduce an algorithm problem that can be solved using a segment tree.\n<\/p>\n \n Write a program that efficiently handles the following two operations on a given integer array.\n<\/p>\n \n The first line contains the size of the array The format of the queries is as follows:<\/p>\n \n Now we will implement a segment tree in C# to solve the above problem.\n<\/p>\n \n The above C# code represents the implementation of a segment tree to solve the given problem. \n The main function takes the size of the array and the number of queries as input, builds the segment tree with the given array, and then, based on the queries, \n In this article, we explored the implementation of a segment tree using C# and how to solve range sum query and update problems. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n In this article, we will explore the basic concepts of segment trees and how to use them through practical problems. Segment trees can be very useful in interval query problems.
\n In particular, they can efficiently handle operations such as range sum, range minimum\/maximum, and range updates.\n<\/p>\nWhat is a Segment Tree?<\/h2>\n
\n It allows for query operations and updates on specific intervals to be processed in logarithmic time complexity.
\n A segment tree is generally structured as a binary tree, where each node stores information about a specific interval.\n<\/p>\nStructure of a Segment Tree<\/h3>\n
\n
Problem Introduction<\/h2>\n
Problem Description<\/h3>\n
\n
Input Format<\/h3>\n
N<\/code> and the number of queries M<\/code>. (1 \u2264 N \u2264 100,000, 1 \u2264 M \u2264 100,000)
\n Following this, N<\/code> integers are given for the array, and then M<\/code> queries are provided.\n<\/p>\n\n
Implementation of Segment Tree<\/h2>\n
\nusing System;\n\nclass SegmentTree\n{\n private int[] tree;\n private int size;\n\n public SegmentTree(int n)\n {\n size = n;\n tree = new int[n * 4]; \/\/ Size of the segment tree\n }\n\n \/\/ Build the tree\n public void Build(int[] arr, int node, int start, int end)\n {\n if (start == end)\n {\n tree[node] = arr[start]; \/\/ Leaf node\n }\n else\n {\n int mid = (start + end) \/ 2;\n Build(arr, node * 2, start, mid); \/\/ Left child\n Build(arr, node * 2 + 1, mid + 1, end); \/\/ Right child\n tree[node] = tree[node * 2] + tree[node * 2 + 1]; \/\/ Update parent node\n }\n }\n\n \/\/ Range sum query\n public int Query(int node, int start, int end, int l, int r)\n {\n if (r < start || end < l)\n {\n return 0; \/\/ Range not evaluable\n }\n\n if (l <= start && end <= r)\n {\n return tree[node]; \/\/ Completely inside\n }\n\n int mid = (start + end) \/ 2;\n int leftSum = Query(node * 2, start, mid, l, r);\n int rightSum = Query(node * 2 + 1, mid + 1, end, l, r);\n return leftSum + rightSum; \/\/ Return sum of both ranges\n }\n\n \/\/ Update\n public void Update(int node, int start, int end, int idx, int val)\n {\n if (start == end)\n {\n tree[node] = val; \/\/ Update leaf node\n }\n else\n {\n int mid = (start + end) \/ 2;\n if (start <= idx && idx <= mid)\n {\n Update(node * 2, start, mid, idx, val); \/\/ Update left child\n }\n else\n {\n Update(node * 2 + 1, mid + 1, end, idx, val); \/\/ Update right child\n }\n tree[node] = tree[node * 2] + tree[node * 2 + 1]; \/\/ Update parent node\n }\n }\n}\n\nclass Program\n{\n static void Main(string[] args)\n {\n int N, M;\n N = int.Parse(Console.ReadLine());\n M = int.Parse(Console.ReadLine());\n\n int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);\n SegmentTree segTree = new SegmentTree(N);\n segTree.Build(arr, 1, 0, N - 1); \/\/ Build segment tree\n\n for (int i = 0; i < M; i++)\n {\n string[] query = Console.ReadLine().Split(' ');\n int type = int.Parse(query[0]);\n\n if (type == 1)\n {\n \/\/ Range sum query\n int l = int.Parse(query[1]) - 1;\n int r = int.Parse(query[2]) - 1;\n Console.WriteLine(segTree.Query(1, 0, N - 1, l, r));\n }\n else if (type == 2)\n {\n \/\/ Update\n int x = int.Parse(query[1]) - 1;\n int y = int.Parse(query[2]);\n segTree.Update(1, 0, N - 1, x, y);\n }\n }\n }\n}\n<\/code><\/pre>\nCode Explanation<\/h2>\n
\n The explanation for each method and class is as follows:\n<\/p>\nClass and Variable Explanation<\/h3>\n
\n
SegmentTree<\/code>: A class representing the segment tree. It takes an array to build the tree and handles range sum queries and updates.<\/li>\ntree<\/code>: An array representing the segment tree. The maximum size of the array is N * 4<\/code>.<\/li>\nBuild<\/code>: A method that constructs the segment tree from the given array.<\/li>\nQuery<\/code>: A method that returns the sum for a given interval.<\/li>\nUpdate<\/code>: A method that updates the value at a given index and reflects changes in the tree.<\/li>\n<\/ul>\nMain Function Explanation<\/h3>\n
\n computes the range sum or performs updates.\n<\/p>\nConclusion<\/h2>\n
\n The segment tree is a powerful tool for efficiently handling interval queries and can be applied to various problems.
\n When faced with problems requiring complex queries or updates, it is advisable to consider using a segment tree.
\n I hope you deepen your understanding of this data structure by solving various practice problems.\n<\/p>\n