Auto comment: topic has been updated by kabirsahni8 (previous revision, new revision, compare).

I don't think you can solve it directly using a segment tree. My approach was:

Find a pair i>j of a[i]-a[j]>=k or a[i]-k>=a[j]. This pair will be counted when r>=i and l<=j or (j+1)*(n-i) times. So the solution looks like this:

1. Compress the range to 1 until n.

2. Use a fenwick tree or segment tree to get a range sum query and do something similar to counting the inversions of an array. You are on a[i] and you need to find all a[j] such that a[i]-k>=a[j] and do (j+1)*(n-i). You have n-i, to get the (j+1) you update the tree on the position of a[i] on the compressed range adding (i+1) there. Use binary search (upper_bound — 1) to find the last position where a[i]-k>=a[j] and do ans+=sum_qry(0, last_position)*(n-i). The arrays are 0-based.

3. Reverse the array and do the same again.