蓝桥杯算法提高VIP-分苹果 （C++代码）

解题思路:

树状数组。套模版，真正需要码的代码只有一小部分。



注意事项:

使用模版二

参考代码:

#include <iostream>
#include <algorithm>
#include<string.h>
using namespace std;
int a[100010],n,w;
int lowbit(int x)
{
    return x&(-x);
}

void add(int i,int x)
{
    while(i<=n){
        a[i]+=x;
        i+=lowbit(i);
    }
}
int sum(int x)
{
    int sum=0;
    while(x>0){
        sum+=a[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{int z,p=0;	
 
	cin>>n;
	cin>>w;
	memset(a,0,sizeof(a));
	for(int i=1;i<=w;i++){
		int a,b,c;
	    cin>>a>>b>>c;
		add(a,c);
		add(b+1,-c);
	}
    for(int i=1;i<=n;i++){
    	if(i>1)cout<<" ";
    	cout<<sum(i);
	} 
    
	return 0;
}