# Java Segment Tree Solution

• Inspired by binary index tree solution, I just wrote a segment tree version.

``````public class Solution {
int n;
int[] nums;
int[] numsSorted;
int[] segmentTree;
public int reversePairs(int[] nums) {
n = nums.length;
nums = nums;
numsSorted = Arrays.copyOf(nums, n);
Arrays.sort(numsSorted);
segmentTree = new int[n * 2];

int res = 0;
for (int val : nums) {
res += search(findIndex(2L * val + 1));
update(findIndex(val));
}
return res;
}

private int findIndex(long val) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (numsSorted[mid] >= val) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}

private int search(int pos) {
int l = pos + n;
int r = n * 2 - 1;
int sum = 0;
while (l <= r) {
if (l % 2 == 1) {
sum += segmentTree[l];
l++;
}
if (r % 2 == 0) {
sum += segmentTree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}

private void update(int pos) {
pos += n;
segmentTree[pos] += 1;
while (pos > 0) {
int l = pos;
int r = pos;
if (pos % 2 == 0) {
r = pos + 1;
} else {
l = pos - 1;
}
segmentTree[pos / 2] = segmentTree[l] + segmentTree[r];
pos /= 2;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.