求救,我的树状数组有毒
  • 板块学术版
  • 楼主zhangshirui
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/11/4 15:01
  • 上次更新2023/11/4 17:31:52
查看原帖
求救,我的树状数组有毒
1040353
zhangshirui楼主2023/11/4 15:01

求救,我的树状数组有毒,区间修改改不动

#ifndef TREE_ARRAY
#define TREE_ARRAY 
#include<bits/stdc++.h>
using namespace std;
class is_not_debug{
	
};
template<typename T,typename vessel=vector<T>>
class tree_array{
	vessel sums,mins,maxs;
	int max_pos=0;
	#define lowbit(x) (x&-x)
	
	void add(int i,T x)
	{
		while(i<=sums.size()){
			sums[i]+=x;
			i+=lowbit(i);
		}
	}
	T Prefix(int k){
		int ans=0;
		while(k){ans+=sums[k];k-=lowbit(k);}
		return ans;
	}
	public:
		tree_array(int len):max_pos(len){
			sums.resize(len+5);
			mins.resize(len+5);
			maxs.resize(len+5);
		}
		tree_array(){}
		const T& operator[](int pos){
			return sum(pos,pos+1);
		}
		void update(int pos,T val){
			T t=val-sum(pos,pos+1);
			add(pos+1,t);
		}
		void push_back(T x){
			sums.push_back(x-x);
			mins.push_back(x-x);
			maxs.push_back(x-x);
			update(max_pos++,x);
		} 
		void update(int begin_pos,int end_pos,T abb_val){
			cout<<"在tree_array.h:"<<40<<"行,update(int begin_pos,int end_pos,T abb_val)处\n"; 
			throw is_not_debug();
			add(begin_pos+1,abb_val);
			add(end_pos+1,-abb_val);
		}
		T sum(int begin_pos,int end_pos){
			return Prefix(end_pos)-Prefix(begin_pos);
		}
}; 
#endif
//end_pos总是超尾元素 
2023/11/4 15:01
加载中...