1
class NumArray {
2
  SegmentTree s;
3

4
  public NumArray(int[] nums) {
5
    s = new SegmentTree(nums);
6
    s.root = s.build(0, s.arr.length, s.arr); // build returns root Node of what it built
7
  }
8

9
  public void update(int index, int val) {
10
    int oldvalue =
11
        s.arr[index]; // Find old value with traditional array, which is O(1) time complexity
12
    s.arr[index] = val; // Set our array so that there will be no contradictions if we ever rebuild.
13
    // If we are going use build function only once, then we don't need to update our traditional
14
    // array.
15
    s.update(s.root, val, index, oldvalue); // Call class' function
16
  }
17

18
  public int sumRange(int left, int right) {
19
    return s.rangeSum(s.root, left, right);
20
  }
21
}
22

23
class Node {
24
  int s; // inclusive label
25
  int e; // inclusive label
26
  int val;
27
  Node left;
28
  Node right;
29
}
30

31
class SegmentTree {
32
  Node root;
33
  int[] arr;
34

35
  SegmentTree(int[] arr) {
36
    this.arr = arr;
37
  }
38

39
  public Node build(int start, int end, int[] arr) {
40
    // Start and End integers have nothing to do with building of our SegmentTree, you may ignore
41
    // them for now
42
    // They are needed for querying and updating, so that we can use binary search.
43
    Node temp = new Node();
44
    if (arr.length == 1) { // which means we are setting a node equal to an element of arr
45
      temp.val = arr[0];
46
      temp.s = start;
47
      temp.e = end - 1; // to make it inclusive
48
    } else if (arr.length == 0 || start > end || start < 0 || end < 0) {
49
      return new Node(); // may be better
50
    } else {
51
      // left = build(start, mid but add 1 if array's length is not divisible by 2, left half of the
52
      // passed array)
53
      temp.left =
54
          build(
55
              start,
56
              (start + end) / 2 + (arr.length % 2 == 1 ? 1 : 0),
57
              Arrays.copyOfRange(arr, 0, arr.length / 2 + (arr.length % 2 == 1 ? 1 : 0)));
58
      // right = build(start, mid but add 1 if array's length is not divisible by 2, right half of
59
      // the passed array)
60
      temp.right =
61
          build(
62
              (start + end) / 2 + (arr.length % 2 == 1 ? 1 : 0),
63
              end,
64
              Arrays.copyOfRange(arr, arr.length / 2 + (arr.length % 2 == 1 ? 1 : 0), arr.length));
65
      temp.val = temp.left.val + temp.right.val;
66
      temp.s = start;
67
      temp.e = end - 1; // to make it inclusive
68
    }
69
    return temp; // return this Node to one upper call so that this can be a child of it's parent
70
  }
71

72
  public int rangeSum(Node node, int l, int r) {
73
    if (node == null) {
74
      // Range is completely outside given range
75
      return 0;
76
    }
77
    if (l <= node.s && node.e <= r) {
78
      // Range is completely inside given range
79
      return node.val;
80
    }
81
    // Range is partially inside and partially outside the given range
82
    int mid = (node.s + node.e) / 2;
83
    int left = 0;
84
    int right = 0;
85
    if (l <= mid) {
86
      // For example let's say root's borders are 0:3, l,r=1:2
87
      // Then mid will be 1, then we will go into both directions because 1<=1, and 2>=1
88
      // Our next calls will be rS(root.left(which is 0:1), 1, 2) and rS(root.right(which is 2:3),
89
      // 1, 2)
90
      // Left call's mid will be mid = (0+1)/2 = 0
91
      // Then 1<=0 ? No it's not, this is why left call's variable named left will be 0
92
      // Then 2>=0 ? Yes, we will call rS(root.left.right(which is 1:1), 1, 2)
93
      // Our left call's right call:
94
      // 1:1 is completely inside 1:2, return the value it holds(equals to arr[1] if our arr is up
95
      // to date)
96
      // Our original call's left will be arr[1]
97
      // Let's calculate our first right function
98
      // With same reasoning, our right function will go to left and be root.right.left(which is
99
      // 2:2)
100
      // Our original call's right will be arr[2]
101
      // Our original/first function will return left + right, which is in fact [1:2] inclusive
102
      left = rangeSum(node.left, l, r);
103
    }
104
    if (r >= mid) {
105
      right = rangeSum(node.right, l, r);
106
    }
107
    return (left + right);
108
  }
109

110
  // What we are doing is, going downwards in our tree while we update the values we touch upon
111
  // We need to update root always, since it is sum of every element
112
  // After that we find mid which is mid value of our current node's start and end(inclusive)
113
  // At first call this will be (0+arr.length)/2 => mid
114
  // If given idx is bigger than mid, then we need to keep searching at right branch
115
  // That is why we call the function with root.right as our new root
116
  // If given idx is smaller and equals to mid, then we search at left branch
117
  // Why did we include equality too? Because I built my tree this way.(where equal things go left)
118
  // If idx is between our root's borders then we will decrease by the old value, increase by the
119
  // new value.
120
  // If root equals null, we won't do anything
121
  // We update our traditional array at above.
122
  public void update(Node root, int value, int idx, int oldvalue) {
123
    if (root == null) {
124
      return;
125
    }
126
    int mid = (root.e + root.s) / 2;
127
    if (idx <= root.e && idx >= root.s) {
128
      root.val -= oldvalue;
129
      root.val += value;
130
    }
131
    if (idx > mid) {
132
      update(root.right, value, idx, oldvalue);
133
    } else if (idx <= mid) {
134
      update(root.left, value, idx, oldvalue);
135
    }
136
  }
137
}