Segment tree for updating a random element in an array and to fetch the sum between two indices. In this program of mine , update and get sum methods do not use recursion.Even build tree can written without using recursion but that would need the use of either an explicit stack or a queue which would render the point of eliminating recursion use…

SegmentTree.java

import java.lang.Math;
import java.util.*;
class SegmentTree
{
    static int n;
    static ArrayList<Integer> ar;
    static int t[];
    static int[] map;
    
    SegmentTree(int n)
    {
        this.n=n;
        ar = new  ArrayList<>(n);
        t  =  new int[2*n-1];
        map=  new int[n];
    }
    
      int generateTree(int s,int e,int i)
        {
            
            if(s==e){ t[i]=ar.get(s); map[s] = i ; }
            else
            {
            int mid=s+(e-s)/2;
            t[i]=generateTree(s,mid,2*i+1)+generateTree(mid+1,e,2*i+2);
            }
            return t[i];
        }
        
        void updateValue(int pos,int val)
        {
            int posInTree = map[pos];
            int parent = posInTree;
            int dif = val - t[posInTree] ;
            while(parent > 0)
            {
             t[parent] += dif;
             parent = (int)Math.ceil(parent/2)-1;             
             }            
          }
        
        int getSum(int str, int end)
        {
            
            int parentL = map[str];
            int parentR = map[end];
            int sumL=t[parentL];
            int sumR=t[parentR];
              while(parentL != parentR)
              {
                 parentL = (int)Math.ceil(parentL/2)-1;
                 parentR = (int)Math.ceil(parentR/2)-1;
            
                 if(parentR%2 == 0)
                  sumR = t[parentR];
              
                 if(parentL%2==1)
                  sumL = t[parentL];
              }
            
            return sumL+sumR;
            
        }
    
    public static void main(String args[])
    {
        SegmentTree st = new SegmentTree(10);
        
        Random rn = new Random();
        for(int i=0;i<10;i++)
        {
            ar.add(rn.nextInt(11));
        }
        
        st.generateTree(0,n-1,0);
        for(int i=0;i<5;i++)
        {
            
            System.out.println("array right now : ");
            for(int x : ar)
            System.out.print(x+" ");
            
            int pos = rn.nextInt(10);
            int value =rn.nextInt(11);
            st.updateValue(pos,value);
            
            System.out.println("\nUpdated array : ");
            for(int j = 0;j<n;j++)
            System.out.print(t[map[j]] + " ");
            
            System.out.println("\nEnter the start and end value for sum : \n");
            int str = rn.nextInt(5);
            int end = rn.nextInt(10);
            if(str > end)
            continue;
            System.out.println("\nsum :" + st.getSum(str,end)); 
            
            
        }
    }
    
}