划分树几道题目 - c++编程基础

主要参考kuangbin博客

个人感觉划分树是基于快速排序的分治的思想，是把快速排序每个过程记录下来而已（借助快速排序也是可以快速求整个区间第k值的）

对于每个区间，找中间值比较分成两个子区间，再递归处理

划分树Hdu4251（区间第k值）

typedef long long LL;
typedef unsigned long long ULL;
typedef vector 
  
    VI;
const int INF = 1000000000;
#define lson l, m, dep + 1
#define rson m + 1, r, dep + 1
const int maxn = 100010;
const int deep = 30;
 
int t[deep][maxn];
int st[maxn];
int toleft[deep][maxn];
 
void build(int l, int r, int dep)
{
   int i;
   if (l == r) return;
   int m = (r + l) >> 1;
   int same = m - l + 1;//表示等于中间值而且被分入左边的个数
   for (i = l; i <= r; i++)
       if (t[dep][i] < st[m])
           same--;
   int lpos = l;
   int rpos = m + 1;
   for (i = l; i <= r; i++)
    {
       if (t[dep][i] < st[m])//比中间的数小，分入左边
           t[dep + 1][lpos++] = t[dep][i];
       else if (t[dep][i] == st[m] && same > 0)
       {
           t[dep + 1][lpos++] = t[dep][i];
           same--;
       }
       else// if (t[dep][i] > st[m]) //比中间值大分入右边
            t[dep + 1][rpos++] = t[dep][i];
       toleft[dep][i] = toleft[dep][l - 1] + lpos - l;//从1到i放左边的个数
    }
   build(lson);
   build(rson);
}
 
//查询区间第k大的数，[l,r]是大区间，[L,R]是要查询的小区间
int query(int L, int R, int k,int l, int r,int dep)
{
   if (l == r) return t[dep][l];///!!!!!!!!!!!!!!!!!!!!!!!!!!!!1
   int m = (l + r) >> 1;
   int cnt = toleft[dep][R] - toleft[dep][L - 1];//[L,R]中位于左边的个数
   if (cnt >= k)
    {
       //l+要查询的区间前被放在左边的个数
       int newl = l + toleft[dep][L - 1] - toleft[dep][l - 1];
       //左端点加上查询区间会被放在左边的个数
       int newr = newl + cnt - 1;
       return query(newl, newr, k, lson);///!!!!!newl, newr
    }
   else
    {
       int newr = R + toleft[dep][r] - toleft[dep][R];
       int newl = newr - (R - L - cnt);
       return query(newl, newr, k - cnt, rson);///!!!!!!
    }
}
 
int main()
{
   int n, m;
   int a, b;
   int p = 1;
   while (cin >> n)
    {
       CLR(t, 0);///
       FE(i, 1, n)///
       {
           RI(t[0][i]);
           st[i] = t[0][i];
       }
       sort(st + 1, st + n + 1);///
       build(1, n, 0);///
       printf("Case %d:\n",p++);
       cin >> m;
       REP(i, m)
       {
           RII(a, b);
           printf("%d\n",query(a, b, (b - a) / 2 + 1, 1, n, 0));
       }
    }
}

划分树hdu 3473 (Minimum Sum )增加了一个lsum【】函数

typedef long long LL;
typedef unsigned long long ULL;
typedef vector 
  
    VI;
const int INF = 1000000000;
const int maxn = 100010;
const int deep = 20;
 
#define lson l, m, dep + 1
#define rson m + 1, r, dep + 1
 
int t[deep][maxn];
int toleft[deep][maxn];
int st[maxn];
LL lsum[deep][maxn];
//LL sum[maxn];
LL ans;
 
void build(int l, int r, int dep)
{
   if (l == r) {
       lsum[dep][l] = t[dep][l];
       return ;
    }
   int m = (l + r) >> 1;
   int same = m - l + 1;
   FE(i, l, r)
    {
       if (t[dep][i] < st[m])
           same--;
       lsum[dep][i] = t[dep][i];
       if (i != l) lsum[dep][i] += lsum[dep][i - 1];
    }
   int lpos = l;
   int rpos = m + 1;
   FE(i, l, r)
    {
       if (t[dep][i] < st[m])
           t[dep + 1][lpos++] = t[dep][i];
       else if (t[dep][i] == st[m] && same > 0)
       {
           t[dep + 1][lpos++] = t[dep][i];
           same--;
       }
       else
           t[dep + 1][rpos++] = t[dep][i];
       toleft[dep][i] = toleft[dep][l - 1] + lpos - l;///
    }
   build(lson);
   build(rson);
}
 
int query(int L,int R, int k, int l, int r,int dep)
{
   if (L == R ) return t[dep][L];
   int cnt = toleft[dep][R] - toleft[dep][L - 1];
   int m = (l + r) >> 1;
 
   int ln1 = toleft[dep][L - 1] - toleft[dep][l - 1];
   int rn1 = L - l - ln1;
 
   int ln2 = cnt;
   int rn2 = R - L + 1 - cnt;
 
   if (cnt >= k)
    {
       if (rn2 > 0)
       {
           if (rn1 > 0)
                ans += lsum[dep + 1][m + rn1 +rn2] - lsum[dep + 1][m + rn1];///@@@@///dep + 1
           else ans += lsum[dep + 1][m + rn2];
       }
 
       int newl = l + ln1;
       int newr = newl + cnt - 1;
       return query(newl, newr, k, lson);
    }
   else
    {
       if (ln2 > 0)
       {
           if (ln1 > 0)
                ans -= lsum[dep + 1][l - 1 +ln1 + ln2] - lsum[dep + 1][l - 1 + ln1];
           else ans -= lsum[dep + 1][l - 1 + ln2];
       }
 
       int newr = R + toleft[dep][r] - toleft[dep][R];
       int newl = newr - (R - L - cnt);
       return query(newl, newr, k - cnt, rson);
    }
 
}
 
int T;
int n, m;
int main()
{
   int x, y;
   cin >> T;
   int p = 1;
   while (T--)
    {
       RI(n);
//       CLR(t, 0,);///
//       CLR(toleft, 0);///
       FE(i, 1, n)
       {
           RI(t[0][i]);
           st[i] = t[0][i];
       }
       sort(st + 1, st + n + 1);
       build(1, n, 0);///
       printf("Case #%d:\n",p++);
       RI(m);
       REP(i, m)
       {
           RII(x, y);
           x++;
           y++;
           ans = 0;
           LL midval = query(x, y, (y - x) / 2 + 1, 1, n, 0);///0
           if ((y - x + 1) % 2 == 0) ans -= midval;
           cout << ans << endl;
       }
       printf("\n");
    }
}

又一解法主要是lsum的处理不同

const int MAXN = 100010;
const int

划分树几道题目(一)