權值線段樹

定義：

權值線段樹，基于普通線段樹，但是不同。

舉個栗子：對于一個給定的數組，普通線段樹可以維護某個子數組中數的和，而權值線段樹可以維護某個區(qū)間內數組元素出現的次數。

在實現上，由于值域范圍通常較大，權值線段樹會采用離散化或動態(tài)開點的策略優(yōu)化空間。單次操作時間復雜度o(log_n)

權值線段樹的節(jié)點用來表示一個區(qū)間的數出現的次數例如：數 1和2 分別出現3次和5次，則節(jié)點1記錄 3，節(jié)點2 記錄5， 1和2的父節(jié)點記錄它們的和8 .

存儲結構：

堆式存儲：rt ,l, r, rt<<! , l, m rt<<1|1 ,m+1, r

結點式存儲 struct Node { int sum ,l , r :};

基本作用：

查詢第k小或第k大。

查詢某個數排名。

查詢整干數組的排序。

查詢前驅和后繼（比某個數小的最大值，比某個數大的最小值）

基本操作：

單點修改 (單個數出現的次數+1)

    void update(int l,int r,int rt,int pos) // 當前區(qū)間范圍 l r 節(jié)點 rt    位置 pos 
    {
        if(l==r) t[rt]++;
        else
        {
            int mid=(l+r)/2;
            if(pos<=mid) add(l,mid,rt*2,pos); else add(mid+1,r,rt*2+1,pos);
            t[rt]=t[rt*2]+t[rt*2+1];
        {
    }

查詢一個數出現的次數

    int query(int l,int r,int rt,int pos)
    {
        if(l==r) return t[rt];
        else
        {
            int mid=(l+r)/2;
            if(pos<=mid) return find(l,mid,rt*2,pos); else return find(mid+1,r,rt*2+1,pos);
        }
    }

查詢一段區(qū)間數出現的次數查詢區(qū)間【x,y]

遞歸+二分

    int query(int l,int r,int rt,int x,int y)
    {
        if(l==x&&r==y) return t[rt];
        else
        {
            int mid=(l+r)/2;
            if(y<=mid) return find(l,mid,rt*2,x,y);
            else if(x>mid) return find(mid+1,r,rt*2+1,x,y);
            else return find(l,mid,rt*2,x,mid)+find(mid+1,r,rt*2+1,mid+1,y);
        }
    }

查詢所有數的第k大值
這是權值線段樹的核心，思想如下：
到每個節(jié)點時，如果右子樹的總和大于等于k kk，說明第k kk大值出現在右子樹中，則遞歸進右子樹；否則說明此時的第k kk大值在左子樹中，則遞歸進左子樹，注意：此時要將k kk的值減去右子樹的總和。
為什么要減去？
如果我們要找的是第7 77大值，右子樹總和為4 44，7?4=3 7-4=37?4=3，說明在該節(jié)點的第7 77大值在左子樹中是第3 33大值。
最后一直遞歸到只有一個數時，那個數就是答案。

    int kth(int l,int r,int rt,int k)
    {
        if(l==r) return l;
        else
        {
            int mid=(l+r)/2,s1=f[rt*2],s2=f[rt*2+1];
            if(k<=s2) return kth(mid+1,r,rt*2+1,k); else return kth(l,mid,rt*2,k-s2);
        }
    }

模板題：

HDU – 1394

給你一個序列，你可以循環(huán)左移，問最小的逆序對是多少？？？

逆序對其實是尋找比這個數小的數字有多少個，這個問題其實正是權值線段樹所要解決的

我們把權值線段樹的單點作為1-N的數中每個數出現的次數，并維護區(qū)間和，然后從1-N的數，在每個位置，查詢比這個數小的數字的個數，這就是當前位置的逆序對，然后把當前位置數的出現的次數+1，就能得到答案。

然后我們考慮循環(huán)右移。我們每次循環(huán)右移，相當于把序列最左邊的數字給放到最右邊，而位于序列最左邊的數字，它對答案的功效僅僅是這個數字大小a[i]-1，因為比這個數字小的數字全部都在它的后面，并且這個數字放到最后了，它對答案的貢獻是N-a[i],因為比這個數字大數字全部都在這個數字的前面，所以每當左移一位，對答案的貢獻其實就是

Ans=Ans-(a[i]-1)+n-a[i]

由于數字從0開始，我們建樹從1開始，我們把所有數字+1即可

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxx = 5005;
int tree[maxx<<2];
inline int L(int root){return root<<1;};
inline int R(int root){return root<<1|1;};
inline int MID(int l,int r){return (l+r)>>1;};
int a[maxx];
void update(int root,int l,int r,int pos){
   if (l==r){
     tree[root]++;
     return;
   }
   int mid=MID(l,r);
   if (pos<=mid){
      update(L(root),l,mid,pos);
   }else {
      update(R(root),mid+1,r,pos);
   }
   tree[root]=tree[L(root)]+tree[R(root)];
}
int query(int root,int l,int r,int ql,int qr){
     if (ql<=l && r<=qr){
        return tree[root];
     }
     int mid=MID(l,r);
     if (qr<=mid){
        return query(L(root),l,mid,ql,qr);
     }else if (ql>mid){
        return query(R(root),mid+1,r,ql,qr);
     }else {
        return query(L(root),l,mid,ql,qr)+query(R(root),mid+1,r,ql,qr);
     }
}
int main(){
  int n;
  while(~scanf("%d",&n)){
    int ans=0;
    memset(tree,0,sizeof(tree));
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]++;
        ans+=query(1,1,n,a[i],n);
        update(1,1,n,a[i]);
    }
    int minn=ans;
    for (int i=1;i<=n;i++){
      ans=ans+(n-a[i]+1)-a[i];
      minn=min(ans,minn);
    }
    printf("%d\n",minn);
  }
  return 0;
}

View Code

進階知識主席樹：http://www.rzrgm.cn/young-children/p/11787490.html

參考博客：https://blog.csdn.net/qq_39565901/article/details/81782611

posted @ 2019-11-03 15:51 Young-children 閱讀(8236) 評論(3) 收藏舉報

刷新頁面返回頂部

Young children

權值線段樹

HDU – 1394

公告