线段树--逆序对模板

 逆序对：比如 2 1就是一个逆序对 ，i<j,但是a[i]>a[j]

 怎么用线段树求逆序对？

 

                                       

 

                      ----->>>               

 

import java.util.Scanner; public class Main { static int n; static final int max=10005; static int arr[]=new int[max]; static int tree[]=new int[max<<2]; public static void update(int node,int l,int r,int a,int b){ if(l==a&&r==b){ tree[node]+=1; return; } int mid=(l+r)>>1; if(a<=mid) update(node<<1,l,mid,a,b); if(b>mid) update(node<<1|1,mid+1,r,a,b); tree[node]=tree[node<<1]+tree[node<<1|1]; } public static int query(int node,int l,int r,int a,int b){ if(l>=a&&r<=b){ return tree[node]; } int mid=(l+r)>>1; if(b<=mid) return query(node<<1,l,mid,a,b); else if(a>mid) return query(node<<1|1,mid+1,r,a,b); return query(node<<1,l,mid,a,b)+query(node<<1|1,mid+1,r,a,b); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); int max=0; for(int i=1;i<=n;i++){ arr[i]=scan.nextInt(); max=Math.max(arr[i], max); } int ans=0; for(int i=1;i<=n;i++){ int a=arr[i]; update(1,1,max,a,a); ans+=(i-query(1,1,max,1,a)); } System.out.println(ans); } }

当然也可以先query区间 a[i+1]，n 已经插入的比它大的个数就是这个数产生的逆序对的个数，再更新

import java.util.Scanner; public class Main { static int n; static final int max=10005; static int arr[]=new int[max]; static int tree[]=new int[max<<2]; public static void update(int node,int l,int r,int a,int b){ if(l==a&&r==b){ tree[node]+=1; return; } int mid=(l+r)>>1; if(a<=mid) update(node<<1,l,mid,a,b); if(b>mid) update(node<<1|1,mid+1,r,a,b); tree[node]=tree[node<<1]+tree[node<<1|1]; } public static int query(int node,int l,int r,int a,int b){ if(l>=a&&r<=b){ return tree[node]; } int mid=(l+r)>>1; if(b<=mid) return query(node<<1,l,mid,a,b); else if(a>mid) return query(node<<1|1,mid+1,r,a,b); return query(node<<1,l,mid,a,b)+query(node<<1|1,mid+1,r,a,b); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); int max=0; for(int i=1;i<=n;i++){ arr[i]=scan.nextInt(); max=Math.max(arr[i], max); } int ans=0; for(int i=1;i<=n;i++){ int a=arr[i]; ans+=query(1,1,max,a,n); update(1,1,max,a,a); } System.out.println(ans); } }