Write a sort tree algorithm in C++
- User
Write a sort tree algorithm in C++
Assistant
Okay, the term "sort tree" isn't standard. However, it most likely refers to a Segment Tree, which is a powerful data structure used for efficiently handling range queries (like sum, minimum, maximum) and point updates on an array.
Here's a C++ implementation of a Segment Tree designed for Range Sum Queries and Point Updates.
Concept:
- Structure: A segment tree is a binary tree where each node represents an interval (or segment) of the original array.
- Root: Represents the entire array interval
[0, n-1]. - Children: If a node represents the interval
[L, R], its left child represents[L, M]and its right child represents[M+1, R], whereM = floor((L+R)/2). - Leaves: Represent single elements of the array, i.e., intervals
[i, i]. - Node Value: Each node stores the aggregate value (in this case, the sum) of the elements within its corresponding interval.
- Array Implementation: Segment trees are typically implemented using an array (often sized
4*nto be safe) where the children of nodeiare at indices2*i(left) and2*i+1(right), assuming the root is at index 1.
C++ Implementation:
#include <vector> #include <iostream> #include <numeric> // For std::accumulate if needed, though not directly used in build // Class to represent the Segment Tree class SegmentTree { private: // The array storing the segment tree nodes' values (sums) std::vector<long long> tree; // Copy of the original array (useful for updates) std::vector<int> original_array; // Size of the original array int n; // --- Helper Functions --- /** * @brief Builds the segment tree recursively. * @param node Index of the current node in the 'tree' array (1-based). * @param start Start index of the segment represented by the current node. * @param end End index of the segment represented by the current node. */ void build(int node, int start, int end) { // Base case: If the segment represents a single element (leaf node) if (start == end) { tree[node] = original_array[start]; } else { int mid = start + (end - start) / 2; // Calculate midpoint safely int left_child = 2 * node; int right_child = 2 * node + 1; // Recursively build the left and right subtrees build(left_child, start, mid); build(right_child, mid + 1, end); // Internal node's value is the sum of its children's values tree[node] = tree[left_child] + tree[right_child]; } } /** * @brief Updates a value in the segment tree recursively. * @param node Index of the current node in the 'tree' array (1-based). * @param start Start index of the segment represented by the current node. * @param end End index of the segment represented by the current node. * @param idx The index in the original array to update (0-based). * @param val The new value. */ void update(int node, int start, int end, int idx, int val) { // Base case: Reached the leaf node corresponding to the index if (start == end) { original_array[idx] = val; // Update the original array copy tree[node] = val; // Update the tree node } else { int mid = start + (end - start) / 2; int left_child = 2 * node; int right_child = 2 * node + 1; // Decide which subtree the index falls into if (start <= idx && idx <= mid) { // Index is in the left child's segment update(left_child, start, mid, idx, val); } else { // Index is in the right child's segment update(right_child, mid + 1, end, idx, val); } // After updating a child, recalculate the current node's value tree[node] = tree[left_child] + tree[right_child]; } } /** * @brief Queries the sum of a given range [l, r] recursively. * @param node Index of the current node in the 'tree' array (1-based). * @param start Start index of the segment represented by the current node. * @param end End index of the segment represented by the current node. * @param l Start index of the query range (inclusive). * @param r End index of the query range (inclusive). * @return The sum of the elements in the range [l, r] within the segment [start, end]. */ long long query(int node, int start, int end, int l, int r) { // Case 1: No overlap // The current segment [start, end] is completely outside the query range [l, r] if (end < l || start > r) { return 0; // Return identity element for sum } // Case 2: Total overlap // The current segment [start, end] is completely inside the query range [l, r] if (l <= start && end <= r) { return tree[node]; } // Case 3: Partial overlap // Recursively query the children and combine results int mid = start + (end - start) / 2; int left_child = 2 * node; int right_child = 2 * node + 1; long long left_sum = query(left_child, start, mid, l, r); long long right_sum = query(right_child, mid + 1, end, l, r); return left_sum + right_sum; } public: /** * @brief Constructor to initialize and build the segment tree. * @param arr The input array. */ SegmentTree(const std::vector<int>& arr) { original_array = arr; n = arr.size(); // Allocate space for the tree. 4*n is usually sufficient. // Using 1-based indexing for nodes, so size needs to accommodate up to ~4n. tree.resize(4 * n, 0); if (n > 0) { build(1, 0, n - 1); // Start building from the root (node 1) for range [0, n-1] } } /** * @brief Public interface to update a value. * @param idx Index in the original array to update (0-based). * @param val The new value. */ void updateValue(int idx, int val) { if (idx < 0 || idx >= n) { std::cerr << "Error: Update index out of bounds." << std::endl; return; } update(1, 0, n - 1, idx, val); } /** * @brief Public interface to query the sum of a range. * @param l Start index of the query range (inclusive, 0-based). * @param r End index of the query range (inclusive, 0-based). * @return The sum of elements in the range [l, r]. */ long long queryRangeSum(int l, int r) { if (l < 0 || r >= n || l > r) { std::cerr << "Error: Query range invalid." << std::endl; // Return 0 or throw an exception based on desired error handling return 0; } return query(1, 0, n - 1, l, r); } }; // --- Example Usage --- int main() { std::vector<int> arr = {1, 3, 5, 7, 9, 11}; SegmentTree st(arr); // Query the sum of range [1, 3] (elements are 3, 5, 7) std::cout << "Initial array: "; for(int x : arr) std::cout << x << " "; std::cout << std::endl; long long sum1 = st.queryRangeSum(1, 3); std::cout << "Sum of range [1, 3]: " << sum1 << std::endl; // Expected: 3 + 5 + 7 = 15 // Update the element at index 2 (value 5) to 6 st.updateValue(2, 6); std::cout << "Updated index 2 to 6." << std::endl; // Query the sum of range [1, 3] again (elements are 3, 6, 7) long long sum2 = st.queryRangeSum(1, 3); std::cout << "Sum of range [1, 3] after update: " << sum2 << std::endl; // Expected: 3 + 6 + 7 = 16 // Query the sum of the entire array [0, 5] long long total_sum = st.queryRangeSum(0, 5); std::cout << "Sum of range [0, 5]: " << total_sum << std::endl; // Expected: 1+3+6+7+9+11 = 37 return 0; }Explanation:
SegmentTreeClass: Encapsulates the logic.treeVector: Stores the sums for each segment. Its size is4*nbecause a binary tree withnleaves can have up to2n-1nodes, and using an array representation might skip indices, requiring up to4nworst-case space.original_arrayVector: Stores a copy of the input array. This is helpful for theupdateoperation, allowing us to easily get the previous value if needed (though not strictly necessary for sum updates) and conceptually track the underlying data.buildFunction:- Takes the current
nodeindex, and thestartandendindices of the segment it represents. - Recursively calls itself for the left (
[start, mid]) and right ([mid+1, end]) segments. - The base case is when
start == end(a leaf node), where it assigns the value fromoriginal_array. - After the recursive calls return, it computes the value for the current node (
tree[node]) by summing the values of its children.
- Takes the current
updateFunction:- Similar recursive structure to
build. - Finds the leaf node corresponding to the index
idxbeing updated. - Updates the value in
original_arrayand the correspondingtreenode. - As the recursion unwinds, it updates the sums of all ancestor nodes on the path from the leaf back to the root.
- Similar recursive structure to
queryFunction:- Takes the current
node, its segment range (start,end), and the query range (l,r). - Handles three cases:
- No Overlap: The node's segment is outside the query range. Return 0 (the identity element for addition).
- Total Overlap: The node's segment is entirely within the query range. Return the precomputed sum stored in
tree[node]. - Partial Overlap: The node's segment partially overlaps the query range. Recursively call
queryon both children and return the sum of their results.
- Takes the current
- Public Methods:
updateValueandqueryRangeSumprovide a clean interface, calling the respective private recursive helper functions starting from the root (node 1) and the full array range[0, n-1].
Complexity:
- Build Time: - Each element is processed roughly constant times during the build.
- Query Time: - Each query traverses the height of the tree, which is logarithmic with respect to
n. - Update Time: - Similar to query, updating involves traversing the height of the tree.
- Space Complexity: - For storing the
treearray.
Other Operations:
This structure can easily be adapted for other associative operations like minimum, maximum, GCD, etc., by changing:
- The identity element returned in the "no overlap" case of
query(e.g., infinity for minimum, negative infinity for maximum). - How the results from children are combined (e.g., using
std::min,std::max). - The value stored in the leaf nodes during
buildandupdate.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.