Update ST

 public class UpdateST {

    public static int tree[];

    public static void init(int n) {

        tree = new int[4 * n];

    }

    public static int construct(int arr[], int i, int start, int end) {

        if (start == end) {

            tree[i] = arr[start];

            return arr[start];

        }

        int mid = (start + end) / 2;

        construct(arr, 2 * i + 1, start, mid);

        construct(arr, 2 * i + 2, mid + 1, end);

        tree[i] = tree[2 * i + 1] + tree[2 * i + 2];

        return tree[i];

    }

    public static void Print() {

        for (int i = 0; i < tree.length; i++) {

            System.out.print(tree[i] + " ");

        }

        System.out.println();

    }

    public static int getSumUtil(int i, int si, int sj, int qi, int qj) {

        if (qj <= si || qi >= sj) {

            return 0;

        } else if (si >= qi && sj <= qj) {

            return tree[i];

        } else {

            int mid = (si + sj) / 2;

            int left = getSumUtil(2 * i + 1, si, mid, qi, qj);

            int right = getSumUtil(2 * i + 2, mid + 1, sj, qi, qj);

            return left + right;

        }

    }

    public static int getSum(int arr[], int qi, int qj) {

        int n = arr.length;

        return getSumUtil(0, 0, n - 1, qi, qj);

    }

    public static void UpdateUtil(int i, int si, int sj, int idx, int diff) {

        if (idx > sj || idx < si) {

            return;

        }

        tree[i] += diff;

        if (si != sj) {

            int mid = (si + sj) / 2;

            UpdateUtil(2 * i + 1, si, mid, idx, diff);

            UpdateUtil(2 * i + 2, mid + 1, sj, idx, diff);

        }

    }

    public static void update(int arr[], int idx, int newVal) {

        int diff = newVal - arr[idx];

        arr[idx] = newVal;

        int n = arr.length;

        UpdateUtil(0, 0, n - 1, idx, diff);

    }

    public static void main(String[] args) {

        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

        int n = arr.length;

        init(n);

        construct(arr, 0, 0, n - 1);

        Print();

        update(arr, 2, 2);

        Print();

    }

}