Point Updates
Given an index, idx, update the value of the array at index idx with value V
The element’s contribution is only in the path from its leaf to its parent. Thus only logN elements will get affected due to the update.
For updating, traverse till the leaf that stores the value of index idx and update the value. Then while tracing back in the path, modify the ranges accordingly.
The time complexity will be O(logN).
Point Update in Segment Tree
Below is the implementation of construction, query, and point update for a segment tree:
C++
// C++ code for segment tree with sum// range and update query#include <bits/stdc++.h>using namespace std;vector<int> A, ST;void build(int node, int L, int R){ // Leaf node where L == R if (L == R) { ST[node] = A[L]; } else { // Find the middle element to // split the array into two halves int mid = (L + R) / 2; // Recursively travel the // left half build(2 * node, L, mid); // Recursively travel the // right half build(2 * node + 1, mid + 1, R); // Storing the sum of both the // children into the parent ST[node] = ST[2 * node] + ST[2 * node + 1]; }}void update(int node, int L, int R, int idx, int val){ // Find the lead node and // update its value if (L == R) { A[idx] += val; ST[node] += val; } else { // Find the mid int mid = (L + R) / 2; // If node value idx is at the // left part then update // the left part if (L <= idx and idx <= mid) update(2 * node, L, mid, idx, val); else update(2 * node + 1, mid + 1, R, idx, val); // Store the information in parents ST[node] = ST[2 * node] + ST[2 * node + 1]; }}int query(int node, int tl, int tr, int l, int r){ // If it lies out of range then // return 0 if (r < tl or tr < l) return 0; // If the node contains the range then // return the node value if (l <= tl and tr <= r) return ST[node]; int tm = (tl + tr) / 2; // Recursively traverse left and right // and find the node return query(2 * node, tl, tm, l, r) + query(2 * node + 1, tm + 1, tr, l, r);}// Driver codeint main(){ int n = 6; A = { 0, 1, 3, 5, -2, 3 }; // Create a segment tree of size 4*n ST.resize(4 * n); // Build a segment tree build(1, 0, n - 1); cout << "Sum of values in range 0-4 are: " << query(1, 0, n - 1, 0, 4) << "\n"; // Update the value at idx = 1 by // 100 thus becoming 101 update(1, 0, n - 1, 1, 100); cout << "Value at index 1 increased by 100\n"; cout << "sum of value in range 1-3 are: " << query(1, 0, n - 1, 1, 3) << "\n"; return 0;} |
Java
// Java code for segment tree with sum// range and update queryimport java.io.*;import java.util.*;class GFG { static int n = 6; static int A[] = { 0, 1, 3, 5, -2, 3 }; // Create a segment tree of size 4*n static int ST[] = new int[4 * n]; public static void build(int node, int L, int R) { // Leaf node where L == R if (L == R) { ST[node] = A[L]; } else { // Find the middle element to // split the array into two halves int mid = (L + R) / 2; // Recursively travel the // left half build(2 * node, L, mid); // Recursively travel the // right half build(2 * node + 1, mid + 1, R); // Storing the sum of both the // children into the parent ST[node] = ST[2 * node] + ST[2 * node + 1]; } } public static void update(int node, int L, int R, int idx, int val) { // Find the lead node and // update its value if (L == R) { A[idx] += val; ST[node] += val; } else { // Find the mid int mid = (L + R) / 2; // If node value idx is at the // left part then update // the left part if (L <= idx && idx <= mid) update(2 * node, L, mid, idx, val); else update(2 * node + 1, mid + 1, R, idx, val); // Store the information in parents ST[node] = ST[2 * node] + ST[2 * node + 1]; } } public static int query(int node, int tl, int tr, int l, int r) { // If it lies out of range then // return 0 if (r < tl || tr < l) return 0; // If the node contains the range then // return the node value if (l <= tl && tr <= r) return ST[node]; int tm = (tl + tr) / 2; // Recursively traverse left and right // and find the node return query(2 * node, tl, tm, l, r) + query(2 * node + 1, tm + 1, tr, l, r); } // Driver Code public static void main(String[] args) { // Build a segment tree build(1, 0, n - 1); System.out.println( "Sum of values in range 0-4 are: " + query(1, 0, n - 1, 0, 4)); // Update the value at idx = 1 by // 100 ths becoming 101 update(1, 0, n - 1, 1, 100); System.out.println( "Value at index 1 increased by 100"); System.out.println("sum of value in range 1-3 are: " + query(1, 0, n - 1, 1, 3)); }}// This code is contributed by Rohit Pradhan |
Python3
# python3 code for segment tree with sum# range and update queryA = []ST = []def build(node, L, R): global A, ST # Leaf node where L == R if (L == R): ST[node] = A[L] else: # Find the middle element to # split the array into two halves mid = (L + R) // 2 # Recursively travel the # left half build(2 * node, L, mid) # Recursively travel the # right half build(2 * node + 1, mid + 1, R) # Storing the sum of both the # children into the parent ST[node] = ST[2 * node] + ST[2 * node + 1]def update(node, L, R, idx, val): global A, ST # Find the lead node and # update its value if (L == R): A[idx] += val ST[node] += val else: # Find the mid mid = (L + R) // 2 # If node value idx is at the # left part then update # the left part if (L <= idx and idx <= mid): update(2 * node, L, mid, idx, val) else: update(2 * node + 1, mid + 1, R, idx, val) # Store the information in parents ST[node] = ST[2 * node] + ST[2 * node + 1]def query(node, tl, tr, l, r): global A, ST # If it lies out of range then # return 0 if (r < tl or tr < l): return 0 # If the node contains the range then # return the node value if (l <= tl and tr <= r): return ST[node] tm = (tl + tr) // 2 # Recursively traverse left and right # and find the node return query(2 * node, tl, tm, l, r) + query(2 * node + 1, tm + 1, tr, l, r)# Driver codeif __name__ == "__main__": n = 6 A = [0, 1, 3, 5, -2, 3] # Create a segment tree of size 4*n ST = [0 for _ in range(4 * n)] # Build a segment tree build(1, 0, n - 1) print(f"Sum of values in range 0-4 are: {query(1, 0, n - 1, 0, 4)}") # Update the value at idx = 1 by # 100 ths becoming 101 update(1, 0, n - 1, 1, 100) print("Value at index 1 increased by 100") print(f"sum of value in range 1-3 are: {query(1, 0, n - 1, 1, 3)}") # This code is contributed by rakeshsahni |
C#
// C# code for segment tree with sum// range and update queryusing System;public class GFG { static int n = 6; static int[] A = { 0, 1, 3, 5, -2, 3 }; // Create a segment tree of size 4*n static int[] ST = new int[4 * n]; public static void build(int node, int L, int R) { // Leaf node where L == R if (L == R) { ST[node] = A[L]; } else { // Find the middle element to // split the array into two halves int mid = (L + R) / 2; // Recursively travel the // left half build(2 * node, L, mid); // Recursively travel the // right half build(2 * node + 1, mid + 1, R); // Storing the sum of both the // children into the parent ST[node] = ST[2 * node] + ST[2 * node + 1]; } } public static void update(int node, int L, int R, int idx, int val) { // Find the lead node and // update its value if (L == R) { A[idx] += val; ST[node] += val; } else { // Find the mid int mid = (L + R) / 2; // If node value idx is at the // left part then update // the left part if (L <= idx && idx <= mid) update(2 * node, L, mid, idx, val); else update(2 * node + 1, mid + 1, R, idx, val); // Store the information in parents ST[node] = ST[2 * node] + ST[2 * node + 1]; } } public static int query(int node, int tl, int tr, int l, int r) { // If it lies out of range then // return 0 if (r < tl || tr < l) return 0; // If the node contains the range then // return the node value if (l <= tl && tr <= r) return ST[node]; int tm = (tl + tr) / 2; // Recursively traverse left and right // and find the node return query(2 * node, tl, tm, l, r) + query(2 * node + 1, tm + 1, tr, l, r); } static public void Main() { // Code // Build a segment tree build(1, 0, n - 1); Console.WriteLine("Sum of values in range 0-4 are: " + query(1, 0, n - 1, 0, 4)); // Update the value at idx = 1 by // 100 ths becoming 101 update(1, 0, n - 1, 1, 100); Console.WriteLine( "Value at index 1 increased by 100"); Console.WriteLine("sum of value in range 1-3 are: " + query(1, 0, n - 1, 1, 3)); }}// This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code for the above approach function build(node, L, R) { // Leaf node where L == R if (L === R) { ST[node] = A[L]; } else { // Find the middle element to split the array into two halves const mid = Math.floor((L + R) / 2); // Recursively travel the left half build(2 * node, L, mid); // Recursively travel the right half build(2 * node + 1, mid + 1, R); // Storing the sum of both the children into the parent ST[node] = ST[2 * node] + ST[2 * node + 1]; } } function update(node, L, R, idx, val) { // Find the lead node and update its value if (L === R) { A[idx] += val; ST[node] += val; } else { // Find the mid const mid = Math.floor((L + R) / 2); // If node value idx is at the left part then update the left part if (L <= idx && idx <= mid) { update(2 * node, L, mid, idx, val); } else { update(2 * node + 1, mid + 1, R, idx, val); } // Store the information in parents ST[node] = ST[2 * node] + ST[2 * node + 1]; } } function query(node, tl, tr, l, r) { // If it lies out of range then return 0 if (r < tl || tr < l) return 0; // If the node contains the range then return the node value if (l <= tl && tr <= r) return ST[node]; const tm = Math.floor((tl + tr) / 2); // Recursively traverse left and right and find the node return query(2 * node, tl, tm, l, r) + query(2 * node + 1, tm + 1, tr, l, r); } // Driver Code const A = [0, 1, 3, 5, -2, 3]; const ST = new Array(4 * A.length); // Build a segment tree build(1, 0, A.length - 1); console.log(`Sum of values in range 0-4 are: ${query(1, 0, A.length - 1, 0, 4)}<br>`); // Update the value at idx = 1 by 100 thus becoming 101 update(1, 0, A.length - 1, 1, 100); console.log(`Value at index 1 increased by 100 <br>`); console.log(`sum of value in range 1-3 are: ${query(1, 0, A.length - 1, 1, 3)}<br>`); // This code is contributed by Potta Lokesh |
Output
Sum of values in range 0-4 are: 7 Value at index 1 increased by 100 sum of value in range 1-3 are: 109
Time complexity: O(N)
- The building operation takes O(N) time
- The query operation takes O(logN) time
- Each update is performed in O(logN) time
Auxiliary Space: O(n)
Note:
A segment tree with 2^x leaf nodes will have 2^(x+1)-1 total nodes due to its perfect binary tree structure. However, when dealing with a non-power-of-two number of elements, extra leaf nodes may be present. To represent all elements, the number of leaf nodes must be rounded up to the nearest power of two, resulting in a maximum of almost 2*n leaf nodes.
For instance, if n is 2^j + 1, 2^(j+1) leaf nodes will be required, leading to an O(2*n) space complexity. As the total number of nodes is about twice the number of leaf nodes, the total space complexity of the segment tree is O(4n). The space requirement can be substantial, but it is usually manageable for most practical applications.
Contact Us