SegmentTree.java

package sw2;

class SegmentTree {
 int[] tree;
 int n;

 public SegmentTree(int[] nums) {
 n = nums.length;
 tree = new int[n * 2];
 buildTree(nums);
 }

 // Построение занимает O(n).
 // Это связано с тем, что нам нужно посетить
 // каждый узел в дереве один раз и вычислить значения сегментов
 private void buildTree(int[] nums) {
 int counter = 0;
 long startTime = System.nanoTime();
 for (int i = n, j = 0; i < 2 * n; i++, j++) {
 tree[i] = nums[j];
 counter++;
 }
 for (int i = n - 1; i > 0; i--) {
 tree[i] = tree[i * 2] + tree[i * 2 + 1];
 counter++;
 }
 long endTime = System.nanoTime();
 long duration = endTime - startTime;
 System.out.println(duration);
 System.out.println(counter);
 System.out.println();
 }
 // Обновление значения занимает O(log n).
 // Это связано с тем, что мы можем пройти по дереву от корня до листьев,
 // используя двоичный поиск, посещая не более n узлов журнала в худшем случае.
 public void update(int pos, int val) {
 int counter = 0;
 long startTime = System.nanoTime();
 pos += n;
 tree[pos] = val;
 while (pos > 0) {
 int left = pos;
 int right = pos;
 if (pos % 2 == 0) {
 right = pos + 1;
 } else {
 left = pos - 1;
 }
 tree[pos / 2] = tree[left] + tree[right];
 pos /= 2;
 counter++;
 }
 long endTime = System.nanoTime();
 long duration = endTime - startTime;
// System.out.println(duration);
// System.out.println(counter);
// System.out.println();
 }
 // Сумма на отрезке тоже занимает O(log n)
 public int query(int l, int r) {
 int counter = 0;
 long startTime = System.nanoTime();
 l += n;
 r += n;
 int sum = 0;
 while (l <= r) {
 if (l % 2 == 1) {
 sum += tree[l];
 l++;
 }
 if (r % 2 == 0) {
 sum += tree[r];
 r--;
 }
 l /= 2;
 r /= 2;
 counter++;
 }
 long endTime = System.nanoTime();
 long duration = endTime - startTime;
// System.out.println(duration);
// System.out.println(counter);
// System.out.println();
 return sum;
 }
}