树状数组

acm

# include<iostream>
# include<string>
# include<algorithm>
#include<numeric>
#include <vector>
#include <queue>
using namespace std;
int c[100];
int b[100];
int n;
int lowbit(int i) {
    return i & (-i);
}
//初始化树状数组c[n]
// c[n] = b[n-0]+b[n-1]+...b[n-(lowbit(i)-1)]
void init() {
    for (int i = 1; i <= n; ++i) {
        int tmp = lowbit(i);
        for (int j = 0; j < tmp; ++j)
            c[i] += b[i - j];
    }
}
// sum(m):返回[1,m]的和
// c[n]代表的是lowbit(n)个b数组元素的和
// c[n] = b[n-0]+b[n-1]+...b[n-(lowbit(i)-1)]
int Sum(int m) {
    int sum = 0;
    while (m > 0) {
        sum += c[m];             //加上lowbit[m]个元素的和
        m -= lowbit(m);          //接着求剩下的 m - lowbit[m]个元素的和
    }
    return sum;
}
// 执行 b[p]+m
//它的父节点都要加m
void Plus(int p, int m) {
    while (p <= n) {
        c[p] += m;
        p += lowbit(p);
    }
}
//测试sum，plus函数
int main1() {
    cin >> n;
    //这里数组下标从1开始
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    init();
    cout << Sum(4);
    system("pause");
    return 0;
}
int main() {
    int at[100];
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
    for (int i = 1; i <= n; ++i)
        at[b[i]] = i;
    int num = 0;
    for (int i = n; i >= 1; --i) {
        int index = at[i];         
        num += Sum(index - 1);     //统计左边有多少个数，左边的数肯定比当前数大，因为是由大到小依次填入数组
        Plus(index,1);
    }
    cout << num;
    system("pause");
    return 0;
}